Psicothema, 1993. Vol. Vol. 5 (nº 1). 135-159

Pilar RUBIO DE LEMUS

En este artículo se ha aplicado parcialmente una metodología de comparación y evaluación de algoritmos de búsqueda de correspondencias en estereopsis. Además se han desarrollado diversas implementaciones de métodos de correspondencias basados en el sistema visual humano: el modelo de Marr y Poggio (1979), el PMF de Pollard, Mayhew y Frisby (1985), el algoritmo de Kim y Aggarwal (1987) y el RP de Rubio de Lemus (1991). Con la aplicación de la metodología de comparación se han confirmado sus posibilidades para ofrecer una serie de resultados sobre los algoritmos al evaluar los aspectos más relevantes de los mismos. Para ello, se han comparado los métodos anteriores en variables del nivel de algoritmo e implementación, analizándose estadísticamente los datos y concluyéndose que el RP y el PMF superan a los otros métodos en eficiencia.

Palabras clave: Metodología; Métodos de búsqueda de correspondencias; Estereopsis; Visión tridimensional; Visión artificial.

Application of a methodology to evaluate matching methods in three-dimensional vision. In this article a methodology to compare and evaluate matching methods in stereopsis is partially applied. Also, the following implementations of matching methods based on the human visual system have been developed: the Marr and Poggio's model (1979), the Pollard, Mayhew and Frisby's PMF algorithm (1985), the Kim and Aggarwal's algorithm (1987) and the Rubio de Lemus' RP algorithm (1991). With the application of the methodology, its possibilities to produce a series of results about the algorithms have been confirmed due to the fact that it evaluates their most relevant aspects. To this aim, these methods have been compared through variables at the algorithm level and the implementation level. The results have been statistically analysed, concluding that RP and PMF are more efficient than the other stereo algorithms.

Key words: Methodology; Matching methods; Stereopsis; Three-dimensional vision; Artificial vision.

La visión tridimensional estereoscópica es un método para estimar la profundidad de una escena y consiste en calcular la distancia que existe entre los objetos o las superficies de los objetos y el observador. Esta distancia se obtiene a partir de las disparidades producidas por la visión binocular. El problema más importante a resolver en estos sistemas es el de encontrar el conjunto de rasgos de una imagen que se corresponden con los de la otra, lo que se conoce como problema de la correspondencia. En este artículo se va a aplicar parcialmente una metodología de evaluación y comparación de sistemas de búsqueda de correspondencias en estereopsis. Esta metodología fue propuesta por Rubio de Lemus (1991) y tiene su base teórica en el enfoque computacional de David Marr (1977), que considera el proceso visual como una tarea de procesamiento de información, lo cual conlleva la diferenciación de éste en tres niveles para su estudio: el nivel de la teoría de cálculo, el de la representación y el algoritmo, y por último, el nivel de la implementación. En el nivel de la "teoría de cálculo" se define lo que se quiere calcular y porqué, así como las condiciones que se deben cumplir para que el proceso quede definido correctamente. En el caso de los sistemas visuales, la tarea consiste en obtener las propiedades del mundo real a partir de las imágenes del mismo que captamos, además de definir las restricciones que, cumpliéndose en el mundo, permiten caracterizar el proceso. El nivel de "representación y algoritmo" está constituído por el cómo se va a realizar el cálculo, lo cual implica encontrar la forma de representar los elementos que va a manejar el sistema (tanto en entrada como en salida) y el algoritmo de transformación. La elección de ambos conceptos depende de diferentes factores (facilidad de manejo, eficiencia) e incluso a veces están interrelacionados. El último nivel lo constituye la "implementación" física del proceso y lógicamente depende de la tecnología disponible. La autora de este trabajo ha elegido este enfoque porque: (1) es una de las teorías más completas para el estudio y comprensión de este tipo de sistemas y (2) ofrece un fundamento teórico a la metodología de trabajo, ya que esta diferenciación facilita el análisis pues los conceptos y detalles que hay que estudiar están perfectamente definidos en cada nivel. Por otro lado, se han desarrollado diversas implementaciones de métodos de correspondencias basados en el sistema visual humano (SVH): el modelo de Marr y Poggio (1979), el PMF de Pollard, Mayhew y Frisby (1985), el algoritmo de Kim y Aggarwal (1987) y el RP de Rubio de Lemus (1991). Estos métodos se describirán brevemente y se compararán en variables del nivel de algoritmo e implementación definidas en la metodología, analizándose posteriormente los resultados.

METODOS DE CORRESPONDENCIAS A EVALUAR

Modelo de Marr y Poggio (1979)

Este modelo es el punto de partida de las tendencias actuales de métodos de estereopsis basados en el SVH. En cuanto a la visión estereoscópica, Marr y Poggio propusieron una teoría basada en la extracción de bordes mediante filtros (con forma de laplaciano de la gaussiana) de distintos tamaños que se convolucionan con las imágenes y la extracción posterior de los puntos de laplaciano nulo (o ceros). El problema de la correspondencia se resuelve utilizando las disparidades obtenidas por los filtros grandes para guiar la búsqueda de correspondencias a resoluciones más finas. Al proceso anterior subyacen tanto la teoría de detección de bordes de Marr y Hildreth (1979), como una serie de restricciones basadas en propiedades sencillas de las superficies que delimitan el problema de la correspondencia para que lo puedan abordar los algoritmos (unicidad, continuidad de las superficies, opacidad). Con estas ideas Marr y Poggio definieron un algoritmo implementado por Grimson (1980, 1984) y Rubio de Lemus (1986). La implementación de Rubio de Lemus de 1986 difería del modelo original de Marr y Poggio en que se recurría a los segmentos que formaban los ceros para desambiguar las correspondencias y sólo se empleaba un tamaño de filtro. Los pasos de la implementación actual (Rubio de Lemus, 1991) del algoritmo original (el cual se va a comparar con los otros métodos) pueden verse en la tabla 1 y se diferencia de la versión de 1986 en que no se recurre a los segmentos, se modifican las características técnicas para facilitar la comparación con los otros métodos (estructuras de datos y rutinas de tratamiento semejantes, etc) y, además, se introduce la restricción de continuidad de las disparidades para detectar errores de emparejamiento. Por otro lado, se ha realizado una implementación modificada de este algoritmo (que también se comparará con los demás métodos), la cual difiere de la implementación original en que trata de solucionar el problema de los emparejamientos múltiples que se producen (varios ceros de la imagen izquierda se emparejan con el mismo de la derecha) e introduce un módulo de similitud figural para caracterizar los emparejamientos potenciales además de usar la similitud de las pendientes y orientaciones de los ceros.

Algoritmo PMF de Pollard, Mayhew y Frisby (1985)

El punto de partida de las teorías de estos autores se sitúa en las investigaciones de Julesz (1971) y en el enfoque computacional del MIT (Marr y Poggio, 1976, 1977, 1979), a partir de las cuales han ido construyendo un cuerpo teórico propio que ha dado como fruto diferentes modelos y algoritmos. El más reciente de ellos es el denominado PMF, el cual basa su funcionamiento en el concepto del límite del gradiente de disparidad (LGD), descubierto en las investigaciones de Burt y Julesz (1980) y que en el PMF se utiliza como restricción para la búsqueda de correspondencias (además de usar también las restricciones de epipolaridad y unicidad implícitamente). Burt y Julesz demostraron que cuando dos puntos de una escena se combinan binocularmente, entonces la razón entre la diferencia de disparidades y su separación ciclópea no supera el valor de 1. Esta razón se denomina gradiente de disparidad. Es importante resaltar dos aspectos del LGD: (1) Burt y Julesz observaron que este límite de 1 sólo se cumple para las combinaciones correctas, de manera que su empleo permitirá seleccionar los emparejamientos adecuados (esto da idea de la gran potencia desambiguadora del LGD) y (2) este límite es importante porque implícitamente incorpora las restricciones de: continuidad de las superficies, continuidad figural y la restricción de orden. En cuanto a la estructura del PMF, éste tiene dos etapas claramente diferenciadas. En la primera se efectúa el cálculo de la fuerza de cada posible emparejamiento. Esto significa que para cada punto de una imagen, se buscan todos los puntos de la otra que pueden combinarse con él y para cada combinación se considera el gradiente de disparidad que tiene con todos los emparejamientos potenciales de los alrededores. Para ver el cálculo de la fuerza del emparejamiento, se va a considerar un punto p de la imagen izquierda.

Este punto puede emparejarse con varios de la imagen derecha. Definiendo una zona alrededor de p de 7 pixeles, se limitan los emparejamientos que van a contribuir a determinar la fuerza de cada una de las posibles combinaciones de p, imponiendo además la restricción de que sólo van a intervenir aquéllas combinaciones potenciales cuyo gradiente de disparidad sea menor o igual a 1 con respecto a aquéllas. Por otro lado, dado que el PMF emplea la restricción de unicidad, se obliga a que cada primitiva de los alrededores contribuya con un solo emparejamiento. Finalmente, otro factor a considerar es el peso de cada contribución. Dado que la probabilidad de encontrar un emparejamiento erróneo que cumpla el límite se incrementa casi de forma lineal al aumentar su separación respecto a la combinación que se está tratando, la contribución a la fuerza del emparejamiento es inversamente proporcional respecto a la distancia entre los pares de puntos. En la segunda etapa del algoritmo, el objetivo es seleccionar para cada primitiva su homólogo a través de un sencillo procedimiento iterativo. En la primera iteración se eligen aquellas combinaciones cuya fuerza de emparejamiento es mayor que ninguna otra de los demás posibles emparejamientos (un cero escoge a su mejor candidato si y sólo si éste no tiene otro mejor pretendiente). Una vez hecho esto y de acuerdo a la restricción de unicidad (que no permite más de una combinación por primitiva), se eliminan todos los emparejamientos potenciales en los que intervenga alguna de las dos primitivas ya combinadas. Esto permite una nueva iteración para seleccionar otros emparejamientos que, tras las eliminaciones, hayan quedado con la mayor fuerza. Generalmente sólo son necesarias tres o cuatro iteraciones para que el algoritmo complete el proceso. Esto ocurre cuando en una iteración ya no se produce ningún emparejamiento más. En la tabla 2 pueden verse los pasos de la implementación de este algoritmo.

Algoritmo de Kim y Aggarwal (1987)

Este algoritmo ofrece los siguientes elementos originales: (1) el uso de la similitud de los patrones de ceros para caracterizar los emparejamientos potenciales (además de usar la características de los ceros) y (2) un proceso de relajación iterativo con probabilidades para la búsqueda de correspondencias. La justificación para emplear un mecanismo de este tipo es que está demostrado que nuestra retina transmite las imágenes al cerebro a través de la excitación de grupos o patrones de células visuales corticales (Levine y Shefner, 1981).

Los patrones de ceros son configuraciones de ceros alrededor de uno dado, cumpliéndose que los ceros que conformen un patrón tengan el mismo signo. Según Kim y Aggarwal existen dieciséis posibles patrones, siendo cualquier otro patrón imposible porque los cambios de luminancia que reflejarían, no podrían darse en la realidad. Con el fin de comparar dos patrones, punto clave del algoritmo, a cada cero del patrón se le da un valor dependiendo de su posición dentro del mismo: el valor de dirección. Cada patrón tiene asociados dos valores de dirección, los cuales se obtienen buscando la posición de los puntos contiguos con el mismo signo en los alrededores y en sentido contrario a las agujas del reloj. Estos valores se utilizan para medir la similitud de los patrones de ceros comparándolos dos a dos, concepto que se calcula hallando la diferencia entre los valores de dirección de los patrones. Para la búsqueda de correspondencias se lleva a cabo un proceso de relajación iterativo basado en probabilidades de emparejamiento que tiene dos partes: (1) la asignación de probabilidades iniciales en función de dos factores: la similitud entre patrones y la similitud entre gradientes, y (2) el cálculo de nuevas probabilidades: éstas se van actualizando para encontrar el mejor candidato mediante un proceso iterativo. Kim y Aggarwal proponen un enunciado general sobre el que se basa este proceso, el cual se concreta luego en tres restricciones: "un punto de una imagen no puede hacerse corresponder en solitario, hay que considerar cómo se empareja su entorno", lo que implica: (1) continuidad de las disparidades, ya que en general las superficies de los objetos son continuas en pequeños contornos, (2) continuidad en los bordes, lo que obliga a que los ceros estén conectados de forma continua a lo largo de los bordes de la figura y (3) continuidad de las probabilidades de correspondencia, que se deduce a partir de los dos puntos anteriores y significa que si los vecinos de un cero tienden a emparejarse, éste se emparejará incluso si su probabilidad de correspondencia es baja. Y al contrario, si los vecinos de un cero no tienden a emparejarse, éste no se emparejará aunque su probabilidad de correspondencia sea alta. Estas tres restricciones se incorporan a la fórmula de relajación básicamente mediante las probabilidades de los puntos conectados. Para cada iteración, las probabilidades superiores a 0.7 dan lugar a emparejamientos correctos, mientras que las inferiores a 0.05 son descartadas para posteriores cálculos . Este proceso iterativo se repite un número determinado de veces (10 en este caso), dependiendo su final bien de una tasa de emparejamientos encontrados, bien de un límite de tiempo determinado por la aplicación real del algoritmo. Los autores proponen que tras el proceso iterativo exista una etapa de desambiguación de los ceros que todavía no se hubieran emparejado, etapa en la que se seleccionarían los emparejamientos con probabilidad mayor que 0.5 y con disparidad semejante a los emparejamientos de los ceros vecinos. Se han realizado dos versiones de este algoritmo. Los pasos de la implementación del algoritmo original pueden verse en la tabla 3, diferenciándose de la implementación modificada en que en esta última se han tratado de solucionar dos problemas: (1) los emparejamientos repetidos y (2) las correspondencias incorrectas producidas por patrones incompletos (creando en este segundo caso una función de similitud del entorno).

Algoritmo RP de Rubio de Lemus (1991)

Este algoritmo tiene dos objetivos: integrar las mejores características de los algoritmos anteriores, así como las modificaciones probadas, e introducir diversos cambios con el fin de hacer el RP lo más eficiente y sencillo posible. El RP ha adoptado de otros algoritmos: (1) los patrones de ceros de Kim y Aggarwal y (2) el esquema iterativo del PMF con el cálculo de la fuerza del emparejamiento a través del LGD. Antes de crear la versión definitiva del RP, se probaron varias ideas con el objeto de reducir el número de operaciones y de mejorar el proceso de selección de emparejamientos simplificando el esquema iterativo. Finalmente se pueden resumir en tres las mejoras que introduce el RP: (1) aumento en la caracterización inicial de los emparejamientos potenciales mediante el uso conjunto de los patrones y la fuerza del emparejamiento, (2) reducción del número de iteraciones del esquema iterativo del PMF y (3) introducción de mecanismos de continuidad figural mediante los patrones, los cuales complementan bien el proceso de emparejamiento. En la figura 1 se puede ver un esquema de la implementación del RP.

Sólo remarcar aquí algunos aspectos en cuanto al proceso iterativo y la aplicación de la continuidad figural y la restricción de orden. Proceso iterativo: para elegir los mejores emparejamientos se considera, además de la fuerza de emparejamiento, la similitud de los patrones y de las orientaciones; la forma de realizar las iteraciones para elegir el mejor candidato es distinta del PMF, ya que el RP intenta combinar la mayor parte de los puntos en la primera iteración en lugar de esperar a las siguientes; el proceso de emparejamiento se completa en dos iteraciones: una tomando de partida la lista de candidatos y la otra la de pretendientes. Continuidad figural: está basada en los patrones y tiene dos funciones: (1) controlar la consistencia de los emparejamientos y (2) resolver los puntos que quedan sin emparejar. Restricción de orden; se comprueba si todos los emparejamientos realizados cumplen la misma.

METODOLOGIA PARA COMPARAR LOS SISTEMAS DE EMPAREJAMIENTO

A continuación se van a detallar las variables de nivel de algoritmo e implementación seleccionadas para comparar y evaluar los métodos de búsqueda que corresponden las en estereopsis. Estas variables se han escogido de la metodología más amplia propuesta por Rubio de Lemus (1991).

Variables de Nivel de Algoritmo

El algoritmo define de forma precisa la manera en que se va a realizar la tarea descrita en la teoría de cálculo. A la hora de evaluar este nivel se han fijado dos objetivos: (1) el análisis funcional para comprobar si éste alcanza los objetivos de la tarea y (2) el análisis del comportamiento del algoritmo.

(1) ANALISIS FUNCIONAL DEL ALGORITMO: en este apartado se evalúa el algoritmo en base a los resultados que obtiene. En el caso de la búsqueda de correspondencias en estereopsis, este análisis se centra en los emparejamientos calculados, objetivo principal del proceso. La forma de estudiar esto es elegir variables que tomando los resultados de cualquier implementación, evalúe aquéllos conceptos que no dependan de la implementación concreta, sino únicamente del algoritmo definido. Para medir los resultados del algoritmo se han seleccionado en este caso las siguientes variables:

* Proporción del total de emparejamientos sobre el total de puntos de la imagen esto es, la proporción de emparejamientos correctos más la proporción de emparejamientos falsos (EC+EF). Este factor mide la capacidad de emparejar del algoritmo (tanto correcta como erróneamente). Esta característica viene determinada por las restricciones definidas en la teoría de cálculo y es independiente de la implementación.

* Proporción de emparejamientos correctos sobre el total de puntos de la imagen (EC). Esta variable relaciona los emparejamientos correctos calculados por el algoritmo con el total de puntos de la imagen. De esta forma se reflejan todos los problemas que conlleva el tratamiento real de una imagen y que van desde puntos que se emparejan en condiciones no previstas por el algoritmo, hasta puntos sin correspondiente, todo ello debido a fallos en el preproceso, condiciones de iluminación especiales, etc.

* Proporción de no emparejamientos correctos sobre el total de puntos de la imagen (NEC). Como normalmente existen puntos que no deben encontrar correspondiente, esta variable mide cuántos de este conjunto no empareja el algoritmo, lo cual también representa un resultado correcto.

* Proporción de emparejamientos correctos sobre los posibles emparejamientos del algoritmo. Esta variable relaciona los emparejamientos obtenidos con todos los emparejamientos correctos que se producen de acuerdo al algoritmo. Esto significa que si en el tratamiento de una imagen hay 90 emparejamientos correctos, pero sólo 80 se ajustan a las condiciones que marca el algoritmo, éste será el conjunto de combinaciones sobre el que se calcula la proporción.

(2) ANALISIS DEL COMPORTAMIENTO DEL ALGORITMO: este análisis se refiere a cómo responde el algoritmo ante un conjunto de condiciones o pruebas a que se somete, con el fin de estudiar aspectos del algoritmo como su robustez o los errores que produce en relación a rasgos de las imágenes. En este caso se va a evaluar la robustez: variable que mide la sensibilidad de las respuestas del algoritmo ante determinados cambios en las condiciones de entrada. Como el resultado de la búsqueda de correspondencias se hace en función de la proporción de emparejamientos correctos, lo que se propone es analizar la fluctuación de esta proporción ante variaciones en las características de las imágenes de entrada. Estas variaciones pueden ser en las condiciones de iluminación, en el número de puntos que componen la escena o en el número de planos de profundidad de la misma. Otra alternativa que se puede emplear es la introducción de ruido en las imágenes, observando la diferencia de resultados del algoritmo entre el tratamiento de las imágenes con y sin ruido. Aquí se va a analizar este concepto mediante la variable proporción de EC+NEC, estudiando cómo responden los algoritmos ante el creciente número de puntos de las escenas.

Variables a Nivel de Implementación

El nivel de la implementación representa la realización práctica del algoritmo mediante un mecanismo concreto. La evaluación que se propone a este nivel se lleva a cabo a través de: (1) análisis de las características de funcionamiento de la implementación y (2) análisis del comportamiento de la misma. Dado que existen múltiples alternativas para construir en la práctica un módulo de búsqueda de correspondencias (programas de ordenador, tarjetas de circuitos, red con dipolos magnéticos), es más difícil poder enunciar variables y conceptos que conciernan a todos estos tipos. Aquí se van a presentar algunos de los aspectos más relevantes en torno a las implementaciones a través de programas de ordenador (que es el caso que nos ocupa).

(1) ANALISIS DE LAS CARACTERISTICAS DE LA IMPLEMENTACIÓN: este concepto se refiere a los rasgos técnicos de la implementación, esto es, cómo se ha realizado en la práctica. Las variables para evaluar las características deben atender a rasgos particulares de cada tipo de implementación. Aquí se va a evaluar el tiempo de procesamiento: esta variable mide el tiempo que ha tardado la implementación en obtener los resultados finales. Aunque el tiempo de proceso es uno de los factores más importantes para la incorporación de estas implementaciones en sistemas de visión artificial (en los que prima la rapidez), hay que tener en cuenta que el tiempo siempre depende tanto del hardware empleado como de los detalles de la implementación concreta. El tiempo de proceso se ha utilizado para optimizar cada implementación y para compararlas. Dado el tipo de máquina empleada, los valores obtenidos sólo sirven de referencia para establecer qué implementación es más rápida y qué fases se podrían mejorar. Para este análisis se han dividido los métodos en dos fases, correspondientes en el caso de Marr y Poggio, del PMF y del RP, al establecimiento de la lista de candidatos y la selección del mejor emparejamiento; en el caso de Kim y Aggarwal, estas fases se corresponden con el cálculo de las probabilidades iniciales y el proceso de relajación.

(2) ANALISIS DEL COMPORTAMIENTO DE LA IMPLEMENTACION: este análisis se refiere a cómo responde la implementación ante un conjunto de pruebas a que se la somete para estudiar aspectos propios de la misma. Aquí se ha elegido la variable robustez: el análisis de este concepto en la implementación es completamente análogo al del algoritmo, excepto que aquí se estudian la sensibilidad ante los cambios en las imágenes de entrada de variables propias de la implementación. Se va a analizar este concepto mediante la variable tiempo de procesamiento, analizando cómo responden las implementaciones ante el creciente número de puntos de las escenas.

ASPECTOS COMUNES EN LA IMPLEMENTACION DE LOS ALGORITMOS

Detalles Comunes de las Implementaciones: (1) se han llevado a cabo sobre un PC.XT trabajando a 10 Mhz. y equipado CON coprocesador matemático, (2) el lenguaje de programación empleado ha sido el TURBO-PASCAL, herramienta que ha permitido utilizar salidas gráficas a pantalla para controlar y comprobar el procesamiento del programa, y (3) en cuanto al tipo de programación, la norma ha sido el tratar de modularizar al máximo, desarrollando cada función en un solo módulo o rutina.

Escenas, Pretratamiento y Representación Tridimensional: se han probado todas las implementaciones con 10 escenas naturales compuestas de objetos geométricos y comunes. En la figura 2 se muestra una de estas escenas (la escena 7) y su pretratamiento, el cual es común a todos los métodos y consiste en transformar las imágenes originales hasta que se dispone de la información necesaria para realizar propiamente el proceso de estereopsis, esto es, la búsqueda de correspondencias y el cálculo de las distancias a los objetos. Los algoritmos parten de la captación de un par de imágenes estereoscópicas mediante dos cámaras montadas en paralelo sobre un eje base, de forma que sólo se produce disparidad horizontal. Asímismo, se extraen los elementos de la imagen o primitivas sobre las que efectuar el proceso de búsqueda de correspondencias, que en este caso son los ceros de las segundas derivadas de los valores de intensidad (o puntos de borde). Los diversos algoritmos filtran y extraen los ceros de las imágenes utilizando el laplaciano de la gaussiana (Marr y Hildreth, 1979) con un sólo tamaño de radio del filtro. Posteriormente, se calculan diversas características de los ceros (módulo o pendiente, signo y dirección) que servirán de ayuda para designar los elementos correspondientes u homólogos.

Después de aplicar los distintos métodos para la búsqueda de correspondencias y con el único objetivo de representar los resultados, se estiman las distancias mediante las disparidades (teniendo en cuenta la geometría de las cámaras) y se realiza una representación tridimensional mediante niveles de gris, donde a mayor distancia de las cámaras, más oscuro y viceversa. En la figura 3 se representan los resultados de las cuatro implementaciones originales sobre la escena 7.

Procedimiento para Calcular los Emparejamientos: para calcular las proporciones de emparejamientos se realizó sobre el papel la correspondencia punto a punto de los 10 pares de imágenes en estéreo a procesar con los diversos métodos, indicando las coordenadas de los ceros de la imagen derecha que debían corresponderse con los de la izquierda. A estas soluciones se las ha denominado "soluciones-patrón" porque son con las que se comparará la solución de cada algoritmo para determinar su rendimiento (validez externa). Por un lado, se determinaron: (a) el número de puntos totales de cada imagen de la izquierda desde los que parte la búsqueda (p.e., escena 7=383 puntos), (b) el número de puntos que se pueden emparejar después de eliminar los puntos que no pueden hacerlo en la imagen derecha porque no existe el cero en la posición que le corresponde (p.e., escena 7=318) y (c) el número de puntos que se pueden emparejar después de eliminar los pares con distinto signo y que los algoritmos no permiten (p.e., escena 7=274). Así pues, se han considerado los siguientes tipos de emparejamientos sobre el número de puntos totales de los que parte la búsqueda:

* puntos emparejados:

-puntos emparejados correctamente (EC)

-puntos emparejados incorrectamente (EF)

* puntos no emparejados:

-puntos no emparejados correctamente (NEC)

-puntos no emparejados incorrectamente (NEF)

Y, por otro lado, estarán los emparejamientos correctos sobre el número de puntos que se pueden emparejar (EC sobre los posibles emparejamientos).

RESULTADOS

A continuación se detallan brevemente los análisis de datos que se han llevado a cabo para comparar los diversos métodos de búsqueda de correspondencias según las variables determinadas por la metodología adoptada:

(1) Resultados a NIVEL de ALGORITMO

(1 .1) Análisis funcional de los algoritmos:

(a) Anova % EC+EF sobre total puntos/imag

(b) Anova % EC+NEC sobre total puntos/imag

(c) Anova % EC sobre posibles

(1.2) Análisis del comportamiento de los algoritmos:

An. Regresión ROBUSTEZ del algoritmo mediante % EC+NEC ante n° puntos/imag

(2) Resultados a NIVEL de IMPLEMENTACION

(2.1) Análisis de las características de las implementaciones:

Anova para tiempos de procesamiento

(2.2) Análisis del comportamiento de las implementaciones:

An. Regresión ROBUSTEZ de la implementación mediante los tiempos de procesamiento ante n° puntos/imag

Resultados a nivel de algoritmo

(1.1) Análisis Funcional de los Algoritmos

(a) Proporciones del Total de Emparejamientos

Con este término nos referimos a las proporciones de emparejamientos correctos y falsos (EC+EF) que producen los diversos algoritmos sobre el total de puntos de la imagen a procesar (estas proporciones pueden verse en la parte superior de la figura 4). Para comprobar si unos algoritmos emparejan significativamente más que otros, se ha llevado a cabo un análisis de varianza con medidas repetidas después de aplicar la siguiente transformación Y'= arcsen/p (Martínez, Maciá y Pérez, 1987, p. 386), con el objeto de corregir las desviaciones de los supuestos paramétricos requeridos para la aplicación del análisis de varianza cuando los datos son proporciones. Tras comprobar que efectivamente se cumplían dichos supuestos, se aplicó el MANOVA del SPSS para el caso de un factor con seis niveles (los diversos algoritmos), obteniéndose diferencias significativas entre los algoritmos (F_5,45=41.01; p<0.001) en proporción del total de emparejamientos. (Este MANOVA, o análisis de varianza multivariado, trata las puntuaciones de cada escena con los diversos algoritmos como si fueran valores de diferentes variables y así produce resultados comparables al análisis de varianza con medidas repetidas (Norusis, 1986, caps. 5 y 6). Para llevar a cabo las comparaciones múltiples, se utilizó el método HSD de Tukey para el caso en que no se cumple el supuesto de circularidad (Hays, 1988, pp. 527-531). En la parte inferior de la figura 4 se expresan los resultados de estas comparaciones dos a dos. Podemos concluir, por lo tanto, que en general, los cuatro algoritmos originales realizan una proporción transformada del total de emparejamientos significativamente mayor que la que realizan los algoritmos modificados (p<0.01), debido a las restricciones que estos últimos incorporan para evitar las repeticiones de emparejamientos. Por su parte, el algoritmo de M&P O, además de ser superior a los modificados también lo es respecto al PMF y al RP, mientras que el RP además es superior al PMF (p<0.01).

(b) Proporciones de Emparejamientos Correctos y No Emparejamientos Correctos.

Se han analizado las proporciones de EC+NEC que producen los diversos algoritmos para estudiar la bondad o corrección de os emparejamientos con respecto a la información total contenida en la imagen de entrada al proceso (estas proporciones pueden verse en la parte superior de la figura 5). Para estudiar si existían diferencias entre los algoritmos se llevó a cabo un análisis de varianza con medidas repetidas (transformando las puntuaciones y comprobando los supuestos del mismo modo que en la variable anterior). En el MANOVA se encontraron diferencias significativas entre los algoritmos (F_5,45=13.12; p<0.001) en proporción de EC+NEC. Se realizaron las comparaciones múltiples por el método HSD de Tukey para medidas repetidas, resumiéndose los resultados en la parte inferior de la figura 5. Podemos concluir que el algoritmo RP es significativamente superior (p<0.0l) en proporción de EC+NEC a todos los demás algoritmos con la excepción del PMF. Este último, a su vez, es significativamente superior (p<0.01) a todos los demás métodos, excepto con respecto al de M&P M. Los otros algoritmos no difieren entre ellos.

(c) Proporción de Emparejamientos Correctos sobre los Emparejamientos Posibles

Esta variable evalúa los EC no respecto al total de puntos de la imagen a procesar (como ocurría en las dos variables anteriores), sino en relación a los que realmente podrían emparejar según las restricciones del algoritmo, esto es, respecto a los puntos de la imagen izquierda que se pueden combinar porque tienen un correspondiente en la imagen derecha y, además, ambos puntos son del mismo signo (pueden verse estas proporciones en la parte superior de la figura 6). Al igual que en las dos variables anteriores se aplicó un análisis de varianza con medidas repetidas (después de transformar las puntuaciones y comprobar los supuestos). En el MANOVA se encontraron diferencias significativas entre los algoritmos (F_5,45=19.0; p<0.001) en proporción de EC sobre los emparejamientos posibles. Realizadas las comparaciones múltiples por el método HSD de Tukey para el caso en que no se cumple el supuesto de circularidad, podemos ver un resumen de los resultados en la parte inferior de la figura 6. Se puede concluir que el algoritmo RP es significativamente superior (p<0.01) en proporción de EC sobre los emparejamientos posibles a todos los demás algoritmos (excepto con respecto al de K&A O al que sólo es superior con p<0.05). Mientras, que el PMF y el algoritmo de M&P O son significativamente superiores (p<0.0l) a las dos versiones modificadas. Los demás algoritmos no difieren entre ellos.

(1.2) Análisis del Comportamiento de los Algoritmos: Robustez Mediante las Proporciones de Emparejamientos Correctos y No Emparejamientos Correctos

Con el propósito de estudiar la robustez de los algoritmos de correspondencia frente a la creciente complejidad de las escenas medida por el número de puntos de las mismas, se llevó a cabo un análisis de regresión para determinar el ajuste de las proporciones de EC+NEC de los diversos métodos a la función lineal. Lo deseable es que el rendimiento de los algoritmos tienda a mantenerse constante a medida que aumenta el número de puntos de las escenas, lo cual significaría que los algoritmos son robustos. En el caso de que hubiera un buen ajuste, se debería comprobar si la pendiente de la ecuación de regresión (b₁) es igual o significativamente distinta de 0 (el que sea igual a 0 equivale a decir que el rendimiento se mantiene constante). En la figura 7 se representan las proporciones de EC+NEC de todos los algoritmos en función de los puntos de las escenas.

Del análisis de regresión lineal realizado para cada método, podemos concluir que el único algoritmo cuyas proporciones de EC+NEC en relación al tamaño de las escenas se ajustaron a la función lineal fue el de K&A O (F_1,8=7.51; p=0.025). Por otro lado, la pendiente de la ecuación lineal de este algoritmo resultó ser significativamente distinta de 0 (t_n-2= -2.747; p=0.025) al aplicar la t de Student, por lo que al ser negativa quiere decir que el algoritmo rinde peor a medida que aumenta el número de puntos de la escena (n=10 escenas). La tendencia de los demás algoritmos (a pesar de no ajustarse a la función lineal) es a estabilizarse tras un mejor rendimiento con las escenas pequeñas y un rendimiento malo con la escena de 156 puntos.

(2) Resultados a nivel de implementación

(2.1) Análisis de las Características de las Implementaciones: Tiempos de Procesamiento

En la figura 8 se representan las medias de los tiempos de proceso de todas las implementaciones para el conjunto de las 10 escenas por fases y el tiempo total. (El análisis de datos se centra únicamente en los tiempos totales ya que es lo que expresa realmente el rendimiento de la implementación, sin embargo, puede resultar interesante observar gráficamente las diferencias entre las fases).

Para analizar las diferencias en tiempos de proceso entre las diversas implementaciones, se llevó a cabo un análisis de varianza con medidas repetidas. Previamente, se contrastaron los distintos supuestos paramétricos y al no ser homogéneas las varianzas (debido a los tiempos de proceso tan elevados y diferentes de las dos implementaciones de K&A con respecto a las demás) se llevó a cabo la transformación logarítmica en base 10 de los tiempos (Winer, 1971, pp. 399-400). Mediante el MANOVA con los tiempos transformados se observaron diferencias significativas entre las implementaciones (F_5,45=519.57; p<0.001). Realizadas las comparaciones múltiples por el test HSD de Tukey para el caso en que no se cumple el supuesto de circularidad, se pueden concluir los resultados de la figura 9. Es decir, las dos implementaciones de K&A emplean un tiempo de procesamiento significativamente mayor (p<0.01) a todos los demás métodos, no existiendo diferencias entre ellas. Por su parte, la implementación de M&P M tarda significativamente más (p<0.01) que el resto de los métodos, mientras que su versión original también emplea un tiempo significativamente superior al PMF y al RP. No existen diferencias significativas entre estas dos últimas implementaciones.

(2.2) Análisis del Comportamiento de las Implementaciones: Robustez Mediante los Tiempos de Procesamiento

Con el objeto de analizar la robustez de cada implementación frente a condiciones cada vez más adversas (ya que así podríamos considerar el tamaño creciente de las escenas medido en número de puntos), se llevó a cabo un estudio sobre el ajuste de los tiempos de procesamiento que emplea cada implementación a las funciones lineal y exponencial, ya que no es lo mismo que los tiempos se ajusten a la función lineal, que el que éstos se disparen exponencialmente cuando aumente el tamaño de la escena. Para observar si unas imágenes requieren más tiempo de procesamiento que otras y cómo son los tiempos por escenas de cada implementación, se pueden representar los datos como en la figura 10, la cual expresa los tiempos de procesamiento de todos los métodos de correspondencia en función del número de puntos de las escenas.

Tras los análisis de regresión, podemos concluir que los tiempos de proceso parecen ajustarse más a la función lineal que a la exponencial, excepto en el caso del RP. Con el objeto de ver si el tiempo de proceso obtenido correlacionaba en el mismo grado con los tiempos pronosticados por la ecuación lineal que con los tiempos pronosticados por la función exponencial, se llevaron a cabo una serie de contrastes de hipótesis para dos coeficientes de correlación con muestras relacionadas. Se llegó a la conclusión de que sólo la implementación de K&A M se ajustaba significativamente mejor a la función lineal que a la exponencial con p<0.01 (t_n-3=6.573; n=10 escenas), mientras que el RP se ajustaba significativamente mejor a la exponencial que a la lineal con p<0.01 (t_n-3= -7.428; n=10 escenas). Este último resultado se debe a que la fase 1 del RP es muy sensible al incremento de puntos de la imagen (esto se puede observar en la tendencia marcada por la escena mayor con 462 puntos).

CONCLUSIONES

La implementación del algoritmo de Marr y Poggio es la más sencilla de todas, ya que no introduce restricciones complejas, ni representa un mecanismo de selección muy elaborado. Su rendimiento es bueno en cuanto a tiempos, pero no en cuanto a la corrección de los emparejamientos que se ven muy afectados por la aparición de combinaciones repetidas. Esto, que la teoría rechaza explícitamente, necesita de reglas concretas para evitarlo en la práctica (como en el PMF). En este sentido se ha creado la versión modificada, que incluye rutinas que impiden este tipo de emparejamientos. No obstante, los resultados aunque han mejorado globalmente considerando EC+NEC, reflejan que el algoritmo no alcanza un nivel excesivamente bueno de combinaciones, lo que puede ser un punto en su contra en aplicaciones prácticas. La razón de este comportamiento hay que buscarla probablemente en la escasa potencia desambiguadora de la restricción de continuidad de las disparidades, restricción que además puede producir muchos errores en determinadas zonas de la imagen (discontinuidades de las superficies) donde no se cumple la regla.

Los resultados de la versión implementada del PMF revelan que el uso de la restricción del límite del gradiente de disparidad como base del proceso de combinación, discrimina perfectamente los emparejamientos correctos e incorrectos, siendo también de gran interés porque su aplicación supone la utilización implícita de otras restricciones ampliamente empleadas en otros algoritmos (orden, continuidad figural). Esta implementación permite una buena resolución del problema de la estereopsis, confirmándose la capacidad desambiguadora de la restricción del límite. Los únicos problemas que se han detectado en la implementación están relacionados con la eficiencia de la misma. Como sería muy compleja la aplicación estricta de la restricción, el PMF propone el uso del mecanismo de la fuerza de la correspondencia como método de incorporación del límite del gradiente en el proceso. A pesar de que el rendimiento conseguido de esta forma es bueno, parece que sería necesario mejorar el tiempo de proceso, sobre todo pensando en aplicaciones prácticas. Los detalles de la implementación del PMF en el sistema TINA (Porrill et al, 1987) confirman estas ideas, apuntando a una reducción del proceso mediante una disminución del número de puntos tratados.

Los resultados de la implementación del algoritmo de Kim y Aggarwal, demuestran que la complejidad de su proceso de relajación le hace ser más lento que los otros y lo que es más importante, perder rendimiento a medida que las imágenes se hacen más complejas o tienen más puntos. La causa de este comportamiento hay que buscarlo en el mecanismo explícito de continuidad que establecen las fórmulas del proceso de relajación (algo que no tienen las otras implementaciones). Con este mecanismo es más fácil que un error en un emparejamiento o la falta de éste, influya en la solución de sus vecinos.

El algoritmo RP representa la síntesis de las mejores características de los tres métodos estudiados, además de incorporar ideas propias sobre el proceso de búsqueda de correspondencias. Puesto que uno de los objetivos planteados al desarrollar el RP era conseguir la mayor sencillez posible (con el fin de lograr el mejor rendimiento), esto se consiguió mediante la supresión de las iteraciones del proceso de relajación del PMF. Los resultados confirman la mejora, ya que el RP presenta una fase 2 más rápida que los otros algoritmos. Además, puesto que también obtiene los mejores resultados a nivel de emparejamientos, se puede afirmar que el rendimiento del RP es claramente superior respecto al resto de los algoritmos estudiados. El análisis de esta mejora revela que la aplicación de los mecanismos de continuidad figural en base a los patrones, complementan bien los emparejamientos obtenidos en el proceso de relajación. La contrapartida a las modificaciones efectuadas, está en el incremento de tiempos de la fase 1, provocado por el aumento de datos en relación a cada posible emparejamiento. Algunas implementaciones en sistemas de visión reales, solucionan este problema resolviendo sólo una parte de los puntos de la imagen, bien para a partir de ellos emparejar los demás por métodos sencillos, bien para dar sólo una solución aproximada.

En resumen, se ha aplicado parcialmente una metodología de comparación de métodos de correspondencia, confirmándose sus posibilidades para ofrecer una serie de resultados sobre los algoritmos al evaluar los aspectos más relevantes de los mismos, y se han desarrollado y optimizado una serie de algoritmos que han concluído en el RP, algoritmo que, junto con el PMF, supera a los otros en eficiencia.

REFERENCIAS

Burt, P. y Julesz, B. (1980). Modifications of the classical notion of Panum's fusional area. Perception, 9, 671-682.

Grimson, W.E.L. (1980). A computer implementation of a theory of human stereo vision. M.I.T. A.I. Lab. Memo, 565, Cambridge, Ma.

Grimson, W.E.L. (1984). Computational experiments with a feature based stereo algorithm. M.I.T. A.I. Lab. Memo 762, Cambridge, Ma.

Hays, W.L. (1988). Statistics. (4ª ed.) New York: Holt, Rinehart and Winston.

Julesz, B. (1971). Foundations of Ciclopean Perception. Chicago: University of Chicago Press.

Kim, Y.C. y Aggarwal, J.K. (1987). Positioning three-dimensional objects using stereo images. IEEE Journal of Robotics and Automation, RA-3, No. 4, 361-373.

Levine, M.W. y Shefner, J.M. (1981). Fundamentals of Sensation and Perception. Readin, Ma.: Addison-Wesley.

Marr, D. (1977). Artificial intelligence a personal view. Artificial Intelligence, 9, 37-48.

Marr, D. y Hildreth, E. (1979). Theory of edge detection. MIT AI Lab. Memo 518.

Marr, D. y Poggio, T. (1976). Cooperative computation of stereo disparity. Science, 194,283-287.

Marr, D. y Poggio, T. (1977). A theory of human stereo vision. M.I.T. A.I. Lab. Memo 451, Cambridge, Ma.

Marr, D. y Poggio, T. (1979). A computational theory of human stereovision. Proc. R. Soc. London Ser. B, 204, 301-328.

Martínez, M. R., Maciá, M.A. y Pérez, J.A. (1987). Psicología Matemática II (Vol. 1). Madrid: Universidad Nacional de Educación a Distancia.

Norusis, M. J. (1986). SPSS/PC+TM Advanced Statistics for the IBM PC/XT/AT and PS/2. Chicago: SPSS Inc.

Pollard, S. B., Mayhew, J. E.W. y Frisby, J. P. (1985). PMF: A stereo correspondence algorithm using a disparity gradient limit. Perception, 14, 449-470.

Porrill, J., Pollard, S. B., Pridmore, T. P., Bowen, J. B., Mayhew, J. E. W. y Frisby, J.P. (1987). TINA: The Sheffield AIVRU vision system. (Al Vision Research Unit). University of Sheffield. Publicado en Proceedings of the Tenth International Joint Conference of Artificial Intelligence, Vol. 2.

Rubio de Lemus, P. (1986). Simulación de la visión estereoscópica humana. Memoria de Licenciatura no publicada, Universidad Complutense de Madrid.

Rubio de Lemus, P. (1991). Análisis Comparativo de Métodos de Correspondencia en Visión Estereoscópica Humana. Tesis Doctoral publicada, Universidad Complutense de Madrid.

Winer, B. J. (1971). Statistical Principles in Experimental Design. (2ª ed.) New York: McGraw Hill.