Visão por Computador

Vista previa del material en texto

Capítulo 1 
IIIINTRODUCCIÓNNTRODUCCIÓNNTRODUCCIÓNNTRODUCCIÓN:::: OBJETIVOS Y OBJETIVOS Y OBJETIVOS Y OBJETIVOS Y 
ESTADO DEL ARTEESTADO DEL ARTEESTADO DEL ARTEESTADO DEL ARTE 
El contexto de la investigación que se recoge en esta memoria 
tiene aspectos de motivación particular, otros de interés del 
grupo de investigación y, los más, de naturaleza científica, 
relacionados con el problema que se aborda y con el estado del 
conocimiento en la materia. 
En este primer capítulo se realiza una introducción al problema 
del seguimiento de objetos y análisis del movimiento. Para una 
mejor comprensión del problema y cómo abordarlo, se han 
revisado numerosos trabajos relacionados con él y se han 
considerado los diversos enfoques de la visión por computador y 
de la visión activa en particular. Se ha profundizado en las 
arquitecturas específicas de visión, revisando, particularmente, 
las dedicadas al seguimiento de objetos y análisis del movimiento. 
El interés de que el procesamiento sea consecuente con las 
restricciones temporales es la razón de que también se haya 
revisado el estado del arte de las arquitecturas de tiempo real. 
CAPÍTULO 1 
 
 
22
La reflexión que constituye este capítulo se completa con una 
propuesta, a grandes rasgos, de resolución del problema que se 
plantea. El resto de la memoria aborda detalladamente dicha 
solución. 
1.11.11.11.1 MMMMOTIVACIÓN Y OBJETIVOTIVACIÓN Y OBJETIVOTIVACIÓN Y OBJETIVOTIVACIÓN Y OBJETIVOSOSOSOS 
1.1.11.1.11.1.11.1.1 PPPPRESENTACIÓNRESENTACIÓNRESENTACIÓNRESENTACIÓN 
Este trabajo se enmarca dentro del proyecto de investigación 
“Sistema de visión para navegación autónoma” parcialmente 
subvencionado por la CICYT (TAP98-0333-C03-03). El objetivo 
principal de este proyecto es el desarrollo de un dispositivo de 
visión artificial para la ayuda a la navegación autónoma. Se 
pretende dotar al sistema de capacidades perceptuales de bajo y 
medio nivel para la extracción e interpretación de información 
acerca del entorno. El dispositivo de visión se considera como un 
periférico inteligente que, a partir de las imágenes captadas, debe 
proporcionar información elaborada. El módulo de procesamiento 
de imagen proporciona filtros y algoritmia para realizar 
operaciones de morfología matemática, segmentación de la 
imagen, extracción de contornos, cálculo de invariantes, 
tratamiento de incertidumbre, identificación de obstáculos,... 
Entre otras tareas, se aborda el análisis de secuencias de 
imágenes. 
Dado que se plantea la integración del módulo de procesamiento 
de visión en el dispositivo, es necesario dotar a este último de 
potencia computacional suficiente para procesar las imágenes a 
frecuencia de video. Este hecho sugiere la necesidad de diseñar 
arquitecturas de alto rendimiento especializadas para los 
problemas de visión. Se tiene interés, asimismo, en el desarrollo 
de modelos de procesamiento en tiempo real, que aporten 
capacidad de refinamiento en la respuesta en función del tiempo 
disponible. 
El tratamiento del procesamiento de tiempo real, en este 
proyecto, se ha tratado a dos niveles: uno, general, a nivel de 
procesamiento hardware (Mora, 2001); y éste, más específico, del 
desarrollo de estructuras de datos sencillas para representar los 
INTRODUCCIÓN: OBJETIVOS Y ESTADO DEL ARTE 
 
 
23 
objetos, cuyo traslado al diseño de arquitecturas especializadas 
sea fácil y cuyo modo de operación contribuya a la rapidez del 
sistema. La integración de ambos trabajos constituirá el prototipo 
de un sistema integral de procesamiento especializado en visión, 
a los niveles bajo y medio, con capacidad de operación en tiempo 
real, de altas prestaciones, derivadas de la flexibilidad de gestión 
de las restricciones temporales a varios niveles; con enfoque de 
miniaturización y empotrabilidad. 
En lo que resta de este primer capítulo se realiza una descripción 
del problema, marcando los objetivos con los que debería 
culminarse el trabajo. Se pasa, a continuación a revisar trabajos 
relacionados con las arquitecturas de visión y de tiempo real. 
Finalmente, a partir de las conclusiones extraídas de lo anterior, 
se presenta una propuesta de solución basada en el modelado 
conexionista. 
En el capítulo 2 se revisan las redes neuronales auto-
organizativas, estudiando su capacidad de preservación de la 
topología. Finalmente, se modifican estos modelos para dotarlos 
de capacidad de operación bajo restricciones de tiempo real. 
En el capítulo 3, se desarrolla la idea de emplear estas redes 
preservadoras de la topología para la representación de los 
objetos. Se presenta, asimismo, una técnica de síntesis de los 
mismos a partir de dicha representación. Como ejemplo de 
aplicación de la caracterización de los objetos, se propone un 
problema de clasificación de formas a partir de su contorno. 
En el capítulo 4 se extiende el uso del modelo desarrollado para 
dotarlo de capacidad de representación del movimiento, de modo 
que se permita el seguimiento de objetos y el análisis de su 
movimiento. Para comprobar la bondad del modelo, se aplica al 
reconocimiento de gestos de la mano. 
Finalmente, en el capítulo 5 se presentan las principales 
conclusiones del trabajo y se plantean las líneas futuras de 
investigación que surgen de él. 
CAPÍTULO 1 
 
 
24
1.1.21.1.21.1.21.1.2 OOOOBJETIVOSBJETIVOSBJETIVOSBJETIVOS:::: DESCRIPCIÓN DEL PRO DESCRIPCIÓN DEL PRO DESCRIPCIÓN DEL PRO DESCRIPCIÓN DEL PROBLEMABLEMABLEMABLEMA 
La navegación de robots basada en información visual requiere el 
análisis de imágenes, con el objetivo de realizar tareas de todo 
tipo, como son la detección del movimiento o la localización y 
seguimiento de objetos. Por ello, el objetivo principal de este 
trabajo es el diseño de un modelo de representación de los 
objetos de una escena, así como de la descripción de su evolución 
a lo largo del tiempo. Este modelo será la base del desarrollo de 
arquitecturas de tiempo real especializadas en visión, por lo que 
debe aportar una estructura de datos eficiente, robusta y de 
sencilla implantación. Aunque el ámbito de aplicación del modelo 
es amplio, se ha particularizado, en este trabajo, para los 
problemas de seguimiento de objetos y análisis de su movimiento. 
Existen diversos factores que determinan la dificultad en la 
resolución del problema de seguimiento de objetos. Un aspecto 
fundamental al desarrollar estructuras de representación de los 
objetos es su forma. Los objetos pueden estar constituidos por 
puntos, aristas, curvas o poseer una morfología libre, con el 
consiguiente incremento de complejidad. 
Por otro lado, la dificultad en el seguimiento de los objetos, 
vendrá dada, principalmente, por la conducta de evolución de los 
mismos. Esta puede ser originada por: 
• cambios morfológicos: los objetos pueden desde ser 
rígidos a presentar modificaciones en su forma, tan 
extremas como su posible disgregación en diversos 
elementos; 
• cambios fotométricos: modificaciones en parámetros, 
tales como la iluminación, afecta a la apariencia visual 
que se tiene del objeto; 
• desplazamientos y giros. 
Usualmente los sistemas de seguimiento de objetos han estado 
restringidos a objetos rígidos. Sin embargo, en la naturaleza la 
mayor parte de elementos en movimiento (el latido de un corazón, 
los ejercicios de un atleta, los movimientos de las nubes,...) no 
cumplen esta restricción. Por esto, en los últimos años existe un 
INTRODUCCIÓN: OBJETIVOS Y ESTADO DEL ARTE 
 
 
25 
creciente interés en el seguimiento de objetos con otros modos de 
movimiento (Kambhamettu et al., 1998). 
El número de objetos a seguir también influye en el desarrollo de 
sistemas de seguimiento. Trabajar con múltiples objetos conlleva 
la iniciación de las estructuras de representación de cada uno 
ellos en lugares adecuados de la escena o la posibilidad de 
división de una estructura original para poder representarlos a 
todos. Además, los objetos pueden tener algún tipo de relación,de modo que los movimientos de unos estén en concordancia con 
movimientos de otros, o ser independientes. 
Las características del entorno afectan considerablemente al 
funcionamiento de los sistemas desarrollados. Cambios en la 
iluminación, presencia de sombras,... crean incertidumbre que 
debe ser manejada correctamente. Esto debe llevar al desarrollo 
de sistemas robustos, que aporten información redundante, de 
modo que se posibilite eliminación de incertidumbre, con el 
inconveniente de un mayor coste computacional. Igualmente, un 
entorno con múltiples objetos en la escena puede dificultar 
considerablemente el seguimiento, ya que pueden poseer 
características visuales similares a las de las entidades objeto de 
interés, pueden producir oclusiones,... 
Por otro lado, el seguimiento de los objetos forma parte de una 
tarea de más alto nivel, el análisis o reconocimiento del 
movimiento. Dentro de éste existen dos vertientes principales: el 
análisis del movimiento basado en el reconocimiento y el 
reconocimiento basado en el movimiento. El primero de ellos está 
determinado por las diversas instancias que el objeto toma a lo 
largo de la secuencia. Por otro lado, el reconocimiento basado en 
el movimiento se fundamenta en el análisis de las trayectorias 
realizadas por el objeto o por partes determinadas del mismo, sin 
prestar atención al reconocimiento del objeto en cada momento. 
Es decir, se realiza un uso directo de la información relativa al 
movimiento de los objetos. 
Con todas estas consideraciones, el objetivo principal de este 
trabajo se sustenta en otras metas intermedias, como son: 
CAPÍTULO 1 
 
 
26
• Desarrollo de un modelo de representación de la 
topología de los objetos con alta capacidad expresiva, 
sencillo de obtener, robusto,... 
• El modelo debe aportar una caracterización de los 
objetos con diferente calidad en la respuesta en función 
del tiempo disponible para su cálculo, de modo que sirva 
como base para el diseño de arquitecturas de visión de 
alto rendimiento que operen bajo restricciones de tiempo 
real. 
• Desarrollo de un modelo de representación del 
movimiento que realice de forma sencilla el seguimiento 
de los objetos y aporte información relevante para el 
análisis de su movimiento, ya sea basado en el 
reconocimiento o basado en el movimiento. 
Para evaluar la capacidad de representación de los objetos, se 
propone un problema de clasificación extrayendo información de 
los contornos de los objetos. Por otro lado, para comprobar el 
funcionamiento del modelo en el tratamiento de secuencias de 
imágenes se plantea una aplicación habitual del análisis del 
movimiento: el reconocimiento de gestos de la mano. 
1.21.21.21.2 EEEESTADO DEL ARTESTADO DEL ARTESTADO DEL ARTESTADO DEL ARTE 
En este apartado se realiza una revisión de aquellos trabajos que 
por tener un fin similar al de esta tesis, pudieran servir como 
base de discusión para desarrollar una solución al problema a 
resolver. Para ello, se ha realizado una primera introducción a los 
problemas de visión por computador y, en particular, al de visión 
activa. Posteriormente se especifican las diversas técnicas de 
seguimiento de objetos y análisis del movimiento. 
Con el objetivo de profundizar en el conocimiento de los aspectos 
relacionados con las arquitecturas de tiempo real especializadas 
en visión, se ha pasado a revisar los trabajos relacionados con 
éstas. 
INTRODUCCIÓN: OBJETIVOS Y ESTADO DEL ARTE 
 
 
27 
1.2.11.2.11.2.11.2.1 VVVVISIÓN POR COMPUTADORISIÓN POR COMPUTADORISIÓN POR COMPUTADORISIÓN POR COMPUTADOR 
El objetivo de la visión por computador es extraer información 
relevante a partir de señal electromagnética del especto visible, 
que pueda ser percibida por sistemas artificiales. Como el ámbito 
de la visión es tan amplio, y también lo es la cantidad de tareas, 
así como su naturaleza y grado de complejidad, es difícil 
establecer una clasificación. En su defecto, usualmente estas 
tareas son englobadas en tres niveles de procesamiento: visión de 
bajo nivel, de nivel medio y de nivel alto. 
Hasta mediados de los 80, el enfoque constructivista pretendía 
reconstruir completamente el mundo, a diversos niveles de 
abstracción, identificando los objetos y sus posiciones, 
obteniendo sus formas a partir de sus colores, sus sombras, su 
movimiento, visión estéreo,... Una vez realizada esta 
reconstrucción tridimensional del entorno, se podían realizar las 
tareas de reconocimiento e interpretación (Marr, 1982). 
La realidad del modesto éxito obtenido incorporó objetividad y 
orientó el planteamiento hacia el enfoque de la visión activa 
(Aloimonos et al., 1988) (Bajcsy, 1988) (Ballard, 1991), en el que 
el procesamiento de visión está dirigido a la tarea a realizar: el 
sistema de visión no es un observador pasivo, sino que adquiere 
las imágenes de forma inteligente. 
Esto conlleva que los sistemas de visión activa, basándose en la 
realimentación de resultados previos, poseen la capacidad de 
controlar los parámetros del dispositivo de visión, tales como 
zoom, enfoque,...; así como de variar la resolución o la frecuencia 
de captura de imágenes. Asimismo, puede ocurrir que sin 
modificar estos parámetros, sí se modifique el modo en el que la 
imagen es procesada posteriormente. 
Tal y como se expresa en (Escolano, 1997), en un sistema de 
visión activa, la percepción debe estar guiada por la acción. Un 
sistema de visión activa no pretende reconstruir el mundo, sino 
enfocar su atención para conseguir aquellas propiedades de la 
imagen que sean necesarias para realizar una tarea determinada, 
obteniendo sistemas más eficientes. 
CAPÍTULO 1 
 
 
28
En particular, respecto del análisis del movimiento, los autores 
coinciden en que éste consiste, en primer lugar, en el seguimiento 
de uno o más objetos y, posteriormente, en la caracterización del 
movimiento realizado, de modo que pueda ser extraída la 
estructura del objeto o se pueda realizar un reconocimiento 
basado en el movimiento (Cédras y Shah, 1995). Las áreas de 
aplicación del análisis del movimiento son muy diversas y abarca 
la interpretación de gestos, sistemas de vigilancia, navegación de 
robots y vehículos, análisis de imágenes médicas, biomecánica, 
compresión de imágenes, video-conferencia,... 
Recientemente, la atención ha ido dirigida, principalmente, al 
tratamiento de movimiento no-rígido (Kambhamettu et al., 1994) 
(Aggarwal et al., 1998), y particularmente al del movimiento 
elástico, esto es, al movimiento no-rígido cuya única restricción 
es un cierto grado de continuidad. 
Entre las técnicas empleadas en el seguimiento de objetos, donde 
más trabajo se está realizando en la actualidad, desde el punto de 
vista algorítmico, es en el desarrollo de modelos de 
representación autónomos o activos, que son empleados 
principalmente en el tratamiento de movimiento no-rígido: snakes 
(Kass et al., 1988) (Terzopoulos y Szelinski, 1992), plantillas 
deformables (Yuille y Hallinan, 1992) (Escolano, 1997), splines 
activos (Curwen y Blake, 1992), superficies activas (Cohen et al., 
1992), cubos activos (Bro-Nielsen, 1994), rayos activos (Denzler y 
Niemann, 1999), formas activas (Cootes y Taylor, 1992),... 
El análisis del movimiento basado en modelos es más limitado, ya 
que requiere un conocimiento previo de las características de los 
objetos, de modo que se pueda realizar un seguimiento de líneas, 
puntos, regiones, etc. que se adapten al modelo (Harris, 1992) 
(Aggarwal y Cai, 1999). 
Asimismo, se ha realizado un importante trabajo en la extracción 
de características más o menos simples (puntos de interés, 
esquinas, aristas,...) y su seguimiento en cada una de las 
imágenes de la secuencia (Sethi y Jain, 1987) (Brady y Wang, 
1992) (Smith et al., 1999), mediante un proceso de 
correspondencia, el cual presenta bastantes problemas y un alto 
coste computacional (Zhang, 1993). 
INTRODUCCIÓN: OBJETIVOS Y ESTADO DEL ARTE 
 
 
29 
Otra técnica muyempleada es la del flujo óptico. Esto es, el 
cálculo de la velocidad de cada uno de los puntos de la imagen 
entre un par consecutivo de imágenes (Beauchemin y Barron, 
1995). 
Por último, existen sistemas que, mediante un proceso de 
correlación, intentan encontrar regiones similares en cada una de 
las imágenes, de modo que se pueda realizar su seguimiento 
(Pratt, 1990) (Eklund et al, 1994). 
La mayor parte de estos trabajos se interesan principalmente en 
proporcionar algoritmos que resuelvan los problemas de visión, 
prescindiendo de incorporar los aspectos de rendimiento, 
estructuración, tecnológicos, etc. como objetivos de su 
investigación. Las soluciones aportadas requieren, en muchos 
casos, potencias computacionales difícilmente viables en la 
actualidad. 
1.2.21.2.21.2.21.2.2 AAAARQUITECTURAS PARA PRRQUITECTURAS PARA PRRQUITECTURAS PARA PRRQUITECTURAS PARA PROCESAMIENTO DE IMAGEOCESAMIENTO DE IMAGEOCESAMIENTO DE IMAGEOCESAMIENTO DE IMAGENNNN 
La visión por computador es uno de los campos de aplicación 
más importantes de la computación paralela (McColl, 1993). Sin 
embargo, para usos modestos y, sobre todo con fines de 
prototipado, algunos autores han profundizado en sistemas 
monoprocesadores. 
El uso de sistemas RISC en problemas de visión es ampliamente 
estudiado en (Baglietto et al, 1996), concluyendo que hasta que 
no se desarrollen compiladores específicos para programas de 
tratamiento de imágenes que generen código optimizado para 
estas tareas, y aumente la velocidad de procesamiento de estas 
arquitecturas, no se podrá lograr un procesamiento en tiempo 
real de las imágenes. 
Se han desarrollado sistemas de seguimiento de objetos y 
detección del movimiento empleando snakes sobre estaciones de 
trabajo UNIX estándar (Denzler y Niemann, 1995), sistemas de 
detección y seguimiento de objetos y personas sobre 
computadores personales Pentium (Fayman et al., 1995) 
(Haritaoglu et al., 1998),... 
CAPÍTULO 1 
 
 
30
Con el objetivo de acelerar las tareas que requieren una gran 
velocidad de cálculo, en los últimos años se han desarrollado 
diferentes tarjetas aceleradoras de procesamiento de imagen de 
alto rendimiento, que ofrecen tasas de respuesta similares a la 
frecuencia de video. Estos sistemas tratan, en su mayoría, 
problemas de visión de bajo nivel. 
Las arquitecturas paralelas empleadas en el tratamiento de 
imagen se basan esencialmente sobre dos principios (Charot, 
1993): el tratamiento segmentado y el paralelismo de datos. 
En líneas generales, las arquitecturas SIMD son apropiadas para 
el procesamiento a bajo nivel, donde redes de elementos de 
procesamiento pueden realizar de forma paralela idénticas 
operaciones sobre diversas zonas de la imagen. Los 
requerimientos del procesamiento a nivel medio sugieren la 
aplicación de computadores MIMD de grano fino, aunque 
también son de aplicación sistemas SIMD. Por último, para el 
procesamiento de alto nivel se requiere una estructura flexible y 
control distribuido para los cálculos y las comunicaciones, por lo 
que los computadores MIMD de grano grueso son los que mejor 
se adaptan. 
Sin embargo, esta clasificación no es generalizada ya que existen 
problemas en los que no está claro el uso de una arquitectura 
específica (Armstrong et al., 1998), e incluso se añaden nuevas 
arquitecturas (Rehfuss y Hammerstrom, 1997) basadas en 
modelos SFMD y SPMD para cubrir el hueco existente entre las 
arquitecturas SIMD y MIMD. Asimismo, el uso de arquitecturas 
híbridas SIMD/MIMD (Helman y Jájá, 1995) permite salvar las 
desventajas de modelos SIMD o MIMD independientes. 
Se han realizado diversos estudios comparativos del 
comportamiento de las diversas arquitecturas ante determinados 
problemas de visión: morfología matemática (Theys, 1996), 
correlación entre imágenes (Armstrong et al., 1998), operaciones 
a bajo y medio nivel (Persa y Jonker, 2000b), histogramas (Bader 
y Jájá, 1994), operaciones a todos los niveles (Ratha y 
Jain,1999),... 
Se han empleado tanto procesadores SIMD de propósito general 
para el tratamiento de problemas de visión como nuevos 
INTRODUCCIÓN: OBJETIVOS Y ESTADO DEL ARTE 
 
 
31 
procesadores paralelos desarrollados específicamente para estas 
tareas. El trabajo a este nivel ha ido encaminado principalmente 
a establecer una red de interconexión entre los elementos de 
procesamiento adecuada para resolver un problema dado. 
Las arquitecturas en malla 2D operan sobre toda la imagen en 
paralelo, dividiéndola en zonas y repartiéndolas entre los 
diferentes procesadores. Si se posee una red de n x n 
procesadores y una imagen de m x m puntos, esa división puede 
ser realizada de dos formas (Figura 1.1): 
1. La imagen se subdivide en ventanas de tamaño n x n, de 
modo que de forma secuencial se barre toda la imagen. 
2. Cada procesador se encarga de ventanas de la imagen de 
tamaño m/n x m/n. 
 
Figura 1.1. Arquitecturas en malla. 
Existen multitud de sistemas de visión basados en esta 
arquitectura, como son MPP de Goodyear (Strong, 1991) y su 
evolución Blitzen (Blevins et al., 1990), DAP de ICL (Parkinson y 
Litt, 1990), GAPP desarrollado por NCR (Cloud, 1988), MP-1 
(Blank, 1990) y MP-2 (Tuck y Kim, 1993) de MasPar, CM-2 de 
Thinking Machines (TMC, 1987), PAPRICA (Broggi et al., 1994a), 
S3PE (Komuro et al.,1997),... 
CAPÍTULO 1 
 
 
32
En el caso de red de interconexión lineal, la imagen es dividida en 
regiones que se asocian a cada uno de los procesadores, que 
suelen corresponder a una columna o a una fila de la imagen a 
procesar. 
Entre los procesadores lineales de tratamiento de imagen se 
encuentran CLIP7 (Fountain et al., 1988), SLAP (Fisher et al., 
1988), la Princeton Engine (Chin et al., 1988), la Sarnoff Engine 
(Knight et al., 1992) y PAPRICA3 (Broggi et al., 1994b) diseñado 
como evolución de PAPRICA. Diversas comparaciones del 
comportamiento de otros procesadores lineales (IMAP-VISION, 
SYMPHONIE, CNAPS, HDPP, SRC-PIM) ante diversas operaciones 
sobre imágenes se pueden encontrar en (van der Molen y Jonker, 
1998) (Le et al., 1998). 
Otro modo de interconectar los elementos de procesamiento es 
mediante una estructura toroidal o helicoidal. Un ejemplo de 
arquitectura SIMD toroidal es el toro polimórfico de IBM (Li y 
Maresca, 1989), cuyos nodos poseen una red interna 
programable, por lo que, en ocasiones, es considerada un 
multiprocesador reconfigurable (Bhandarkar y Arabnia, 1997). 
Un sistema toroidal que conecta FPGA’s formando un toroide 
para realizar el procesamiento de la imagen es la máquina 
reconfigurable PARTS (Woodfill y von Herzen, 1997). 
Arquitecturas de procesadores SIMD en hipercubo son empleadas 
en la Connection Machine (Little et al., 1987) y VisTA (Sunwoo y 
Aggarwal, 1991). 
Una de las arquitecturas más empleada en tratamiento de 
imagen son los procesadores piramidales. Una estructura en 
pirámide establece diversos niveles de representación de las 
imágenes, de modo que éstas puedan ser tratadas con baja 
resolución, empleando pocos datos, para proceder 
posteriormente, si es necesario, a un refinamiento y verificación 
de los resultados a una mayor resolución. Esto aporta diversas 
ventajas (Camus, 1994) (Prewer, 1995) como son: reducción del 
coste de procesamiento, extracción de características globales de 
la imagen, reducción de la complejidad de la comunicación entre 
los procesadores,... Sin embargo, también existen desventajas 
como la dificultad para su implementación VLSI, lo que hace que 
INTRODUCCIÓN: OBJETIVOS Y ESTADO DEL ARTE 
 
 
33 
en muchas ocasiones algoritmos piramidales sean ejecutados en 
arquitecturas hipercubo. 
Una de las primeras arquitecturas piramidales fue PCLIP 
(Tanimoto, 1984). Otros ejemplos son: GAM (Schaefer et al., 
1987), SPHINX (Mérigot et al., 1986), la pirámide del EGPA 
(Fritsch, 1986), SCOOP (Barad, 1988), WPM (Nudd et al., 1989), 
PAPIA (Cantoni et al., 1991) y su evolución PAPIA2 (Biancardi et 
al., 1992). 
Aunque todas las topologías revisadasson ampliamente 
utilizadas en visión por computador, no se ha probado que 
alguna de ellas sea capaz de resolver todos los problemas de 
visión. Recientemente, están apareciendo multiprocesadores 
reconfigurables que permiten modificar la topología de su red de 
interconexión, los cuales para ser factibles deben poseer las 
siguientes propiedades (Bhandarkar y Arabnia, 1997): 
• los nodos deben poseer en cada momento un grado de 
conectividad razonable y la red debe mantener un 
diámetro bajo, para que los enlaces de comunicación no 
crezcan rápidamente, 
• el hardware y el algoritmo de reconfiguración deben 
tener una complejidad baja para no ralentizar el sistema. 
Dentro de estos procesadores reconfigurables se encuentran 
algunos de los ejemplos ya expuestos de otras arquitecturas 
como CLIP7, el toro polimórfico y el sistema piramidal PAPIA2; así 
como nuevos sistemas como RBA (Miller et al., 1988), PARBS 
(Wang et al., 1991), CRAPS (Kao et al., 1993), RMA (Miller et al., 
1993), RMRN (Bhandarkar y Arabnia, 1997), VFE-200 
(Mandelbaum et al., 1998). 
Las arquitecturas MIMD de grano medio y grano grueso son 
adecuadas para el tratamiento de imagen a nivel medio y alto, ya 
que estos problemas requieren la ejecución asíncrona de 
múltiples tareas cooperantes. Los transputers han sido muy 
empleados como bloques constituyentes en una arquitectura 
MIMD, dando lugar a sistemas como las cabezas KTH (Uhlin et 
al., 1995) y Yorick 11-20 (Sharkey et al., 1993). Entre las 
máquinas MIMD que emplean DSP’s como elementos de 
CAPÍTULO 1 
 
 
34
procesamiento se encuentran HMFV (Du et al., 1996), la cabeza 
Yorick 5-5C (Sharkey et al., 1995), la cabeza PennEyes (Cahn von 
Seelen, 1997). Por otro lado, se encuentran también las 
máquinas de flujo de datos como DFCC (Quénot y Zavidovique, 
1992). 
Muchos de los problemas de visión requieren un particular modo 
de operación (SIMD o MIMD) para su ejecución. Una deficiencia 
de las máquinas MIMD típicas, en comparación con los SIMD, es 
que no proveen soporte para coordinación y sincronización entre 
conjuntos de procesadores, por lo que para simular operaciones 
SIMD, la sobrecarga en la comunicación puede ser mayor que el 
tiempo de procesamiento de tareas de bajo nivel. Por ello, una 
máquina que permita cambiar dinámicamente entre ambos 
modos de paralelismo se adaptará mejor a la resolución de un 
mayor número de tareas de visión. Ejemplos de arquitecturas 
híbridas son NETRA (Choudhary et al., 1993), PASM (Siegel et al., 
1996), APVIS (Kim et al., 1998) que hace uso del procesador 
SIMD MPA, Execube (Kogge, 1994), MeshSP (I.C.E., 1995), GCN 
(Jonker, 1993), GFLOPS (Houzet y et al., 1991). 
Una máquina híbrida de propósito general ampliamente utilizada 
en procesamiento de imagen es CM-5 (Leiserson et al., 1994) que 
amplía las anteriores máquinas de Connection Machine, 
dotándolas de modo de procesamiento SPMD. Se ha empleado 
para el cálculo de la transformada de Hough (Baumann y Ranka, 
1992), detección de contornos, aproximación lineal y 
reconocimiento de objetos (Prasanna et al., 1993),... Splash2 
(Ratha y Jain, 1997), construida con FPGA’s, ha sido utilizada en 
tareas de visión a todos los niveles: convoluciones, segmentación 
de textos y reconocimiento de huellas (Ratha y Jain, 1999). 
MORRPH (Drayer et al., 1995) emplea, asimismo, una malla de 
FPGA’s que puede funcionar como máquina SIMD, MIMD o 
segmentada. 
Entre las máquinas segmentadas empleadas para tratamiento de 
imagen se encuentran MITE (Kimmel et al., 1985), PIPE (Kent et 
al., 1985), Acadia (van der Wal et al., 2000). El uso de DSP’s 
como elementos de procesamiento en máquinas segmentadas se 
ha extendido, dando lugar a máquinas como GPIP (Heada et al., 
1988), ISHTAR (Shiohara et al., 1993). 
INTRODUCCIÓN: OBJETIVOS Y ESTADO DEL ARTE 
 
 
35 
Dentro de esta categoría también pueden ser incluidas aquellas 
máquinas, que por realizar tareas de visión a varios niveles, 
desde bajo a alto nivel, combinan diversos módulos con 
arquitecturas SIMD y/o MIMD. Estos sistemas tienen como 
objetivo el realizar un reconocimiento o clasificación de los 
objetos, un seguimiento de los mismos, determinación de la 
estructura a partir del movimiento, etc. Dentro de este tipo de 
máquinas, los sistemas PARADOX (Brady y Wang, 1992), del 
Surrey Attentive Robot (Pretlove y Parker, 1993), IUA (Weems et 
al, 1989) y su evolución IUA2 (Weems, 1993), Vision Engine 
(Little et al., 1991), del Fraunhoffer Institut-IITB de Karlsruhe y 
del ENSPS de Estrasburgo (Hirsch, 1993), ESCHeR (Kuniyoshi et 
al., 1995); combinan un módulo SIMD, ya sea una arquitectura 
desarrollada específicamente o una tarjeta aceleradora de 
propósito especial, para el tratamiento de las imágenes a bajo 
nivel y una red de transputers o DSP’s (módulo MIMD) para un 
procesamiento a más alto nivel. 
1.2.31.2.31.2.31.2.3 AAAARQUITECTURAS PARA SERQUITECTURAS PARA SERQUITECTURAS PARA SERQUITECTURAS PARA SECUENCIAS DE IMÁGENESCUENCIAS DE IMÁGENESCUENCIAS DE IMÁGENESCUENCIAS DE IMÁGENES 
Dado que el análisis del movimiento y, por tanto, del seguimiento 
de objetos, incorpora operaciones de visión por computador a 
todos los niveles, desde el bajo nivel (filtrados, flujo óptico, 
correlaciones,...), pasando por el medio (segmentación, 
parametrización de trayectorias,...) y hasta llegar al alto nivel 
(estructura a partir del movimiento, reconocimiento basado en el 
movimiento,...); una amplia mayoría de las arquitecturas 
diseñadas específicamente con estos objetivos comprenden 
diversos módulos que combinan estructuras SIMD y MIMD. 
Hasta el presente, es escaso el desarrollo de arquitecturas 
específicas. Cuando el objetivo es el desarrollo de una 
arquitectura para ser incorporada en un sistema con altas 
restricciones temporales, suelen emplearse tarjetas comerciales 
para la aceleración de las tareas de bajo nivel. En otros casos, se 
emplean arquitecturas de visión segmentadas compuestas de 
máquinas SIMD y MIMD. En el menor número de casos, se 
desarrollan arquitecturas específicas para el seguimiento de 
objetos. 
CAPÍTULO 1 
 
 
36
La mayor parte de las propuestas emplean métodos basados en el 
cálculo del flujo óptico para la tarea de seguimiento de objetos. 
Estos sistemas comprenden dos partes: a bajo nivel, se realiza el 
cálculo del flujo óptico a partir de una secuencia de imágenes 
siguiendo alguna de las diversas técnicas para su obtención 
(Beauchemin y Barron, 1995). A alto nivel, a partir de dicho flujo 
óptico se obtienen medidas como posición del objeto en 
movimiento, tiempo y dirección de impacto,... que permiten el 
análisis del movimiento. Estas arquitecturas suelen emplear 
transputers o DSP’s para todos los niveles de procesamiento (Mae 
et al., 1994) (Mittal et al., 1995) (Röwekamp et al., 1997). En 
aquellas arquitecturas que tienen en consideración los diversos 
niveles de procesamiento, no se desarrollan arquitecturas a bajo 
nivel sino que se emplean tarjetas comerciales (Tucakov et al., 
1996) (Rougeaux y Kuniyoshi, 1997). 
Asimismo, existen multitud de soluciones basadas en la 
correspondencia entre puntos de interés. La mayor parte de estos 
sistemas sigue la misma filosofía: un módulo SIMD realiza las 
tareas de procesamiento a bajo nivel para mejorar la calidad de la 
imagen y un módulo MIMD, formado por transputers o DSPs, 
realiza la extracción y el seguimiento de los puntos o 
características de interés. Estos características suelen ser aristas 
(Rygol et al., 1992) (Balkenius y Kopp, 1996) (Asaad et al., 1996), 
esquinas (Brady y Wang, 1992) (Beymer et al., 1997) o puntos 
significativos del objeto (Persa y Jonker, 2000a). 
Otros autores realizan el seguimiento de los objetos mediante el 
reconocimiento de puntos o regiones, obtenidas mediante la 
aplicación a la imagen de operaciones de bajo nivel, como pueden 
ser diferencias, operaciones de morfología matemática,... 
Mediante técnicas de correlación o de reconocimiento de patrones 
se localizan los objetosen cada una de las imágenes, para 
realizar su posterior seguimiento (Bertozzi y Broggi, 1998) 
(Castrillón et al., 1998) (Hernández et al., 1999). No existen 
muchos sistemas basados en estas técnicas, ya que son bastante 
limitadas. Además, la productividad de las arquitecturas 
desarrolladas no es muy elevada. 
Por otro lado, apenas existen arquitecturas desarrolladas 
siguiendo las técnicas de representaciones activas, resaltándose 
este hecho en la literatura (Denzler y Niemann, 1995). En 
INTRODUCCIÓN: OBJETIVOS Y ESTADO DEL ARTE 
 
 
37 
(Curwen y Blake, 1992) se presenta una solución de los 
contornos dinámicos basados en splines, donde una red de 
transputers realiza la predicción de la nueva posición del 
contorno, así como su adaptación a la posición correcta. 
Recientemente, se han propuesto computadores en rejilla (Case et 
al., 2001). Estas arquitecturas están formadas por elementos de 
procesamiento que pretenden representar un espacio n-
dimensional, de modo que cada uno de ellos está colocado en un 
punto del espacio, conectados entre sí por canales de 
comunicación bidireccionales formando una rejilla. Este sistema 
ha sido empleado para realizar el seguimiento de objetos con 
movimiento uniforme, marcando aquellos elementos de 
procesamiento en los que está situado el objeto (Shende, 1991). 
Mediante comunicaciones bidireccionales entre procesadores 
vecinos se indica la nueva posición del objeto, de modo que la 
secuencia de procesadores activados determina el movimiento 
seguido por el objeto. 
1.2.41.2.41.2.41.2.4 AAAARQUITECTURAS DE TIEMRQUITECTURAS DE TIEMRQUITECTURAS DE TIEMRQUITECTURAS DE TIEMPO REALPO REALPO REALPO REAL 
Estas arquitecturas previas realizan su operación a altas 
velocidades, de modo que pueden operar bajo las restricciones 
temporales que introduce tener que procesar las imágenes a 
frecuencia de video. Sin embargo, se echa en falta que ajusten 
sus respuestas en función del tiempo disponible. Por ello, en este 
punto se revisan los trabajos relacionados con el desarrollo de 
arquitecturas de tiempo real. 
La característica fundamental que distingue el procesamiento en 
tiempo real de otros tipos de procesamiento es la duración de las 
operaciones y las consecuencias que se derivan de ello (Stankovic 
y Ramamritham, 1990) (Butazzo1997). 
Diversos autores (Ramamritham et al., 1990) (Stankovic, 1992) 
(Niehaus, 1994) (Weems y Dropsho, 1994) (Krishna y Shin, 1997) 
encuentran en lo anterior la mayor dificultad para el desarrollo 
de procesadores específicos para tiempo real: el objetivo principal 
en la mayoría de los diseños de procesadores actuales es 
maximizar el rendimiento medio de las operaciones, tolerándose 
retrasos importantes si los eventos que los producen son poco 
CAPÍTULO 1 
 
 
38
probables. En cambio, en los sistemas de tiempo real se deben 
asegurar las cotas máximas de los tiempos de ejecución. Esto 
significa que una varianza potencialmente grande en los 
rendimientos del procesador sitúa al peor caso en una cota 
demasiado baja, reduciendo la capacidad global del procesador 
para tiempo real en aras de garantizar el resultado en un tiempo 
predeterminado. En definitiva, los procesadores adecuados para 
tareas de tiempo real necesitan de hardware de alto rendimiento 
en el que los tiempos de respuesta, en el peor caso, se aproximen 
al caso promedio (Tokhi, 1998). 
Algunos ejemplos extraídos de los diseños de procesadores 
existentes en los que la predecibilidad en los tiempos de 
respuesta se ve perjudicada (Niehaus, 1994) (Hennessy y 
Patterson, 1996) (Tokhi, 1999) son los siguientes: los 
encaminamientos de datos condicionales, que dependen de que 
se haya predicho el cauce correcto o no (Knieser y Papachristou, 
1992); las instrucciones de latencia variable, dependientes de la 
naturaleza de los operandos (Atkins, 1991); los coprocesadores 
asíncronos que tienen tiempos de comunicación variable (TI, 
1991); las traducciones de las direcciones de memoria, acceso a 
datos e instrucciones, sufren variaciones en los tiempos debido al 
uso de buffers (TLB —Table Lookaside Buffer), (DEC, 1992) 
(Thomson y Ryan, 1994). 
Las implicaciones de los sistemas de tiempo real en el nivel del 
procesador se concretan en aportar soluciones con respecto a la 
predecibilidad y a la reducción de la inestabilidad temporal en la 
ejecución de sus operaciones. Sin embargo, a estos niveles se 
deja pendiente el desarrollo de esquemas de control sobre esta 
incertidumbre temporal, que proporcionen al diseñador y 
programador, elementos de ayuda para satisfacer las demandas 
impuestas por estos sistemas, sin tener que sacrificar el 
rendimiento del mismo. 
El reflejo de esta situación se sustancia en las líneas actuales de 
investigación en el terreno de los sistemas de tiempo real (Son, 
1995) donde predominan, sin lugar a dudas, las propuestas de 
nivel alto y escasean las referidas a arquitecturas de 
computadores: 
INTRODUCCIÓN: OBJETIVOS Y ESTADO DEL ARTE 
 
 
39 
1. Métodos formales de especificación y verificación de 
requerimientos (Hennessy y Reagan, 1991) (Nicollin y 
Sifakis, 1991) (Nanda et al., 2000). 
2. Herramientas y lenguajes de programación para soportar 
el desarrollo de procesos predecibles cada vez más 
potentes (Flex, RTC++, RT-Euclid,...) (Stoyenko, 1987) 
(Bihari y Gopinath, 1991) (Kenny y Lin, 1991). 
3. Sistemas operativos (Ready, 1986) (Holmes et al., 1987) 
(Hull et al., 1996), entornos complejos y poco predecibles 
como los sistemas distribuidos y multiprocesador 
HARTOS (Kandlur et al., 1989), SPRING (Stankovic y 
Ramamritham, 1991), CHAOSarc (Gheith y Schwan, 
1993), Maruti-II (Son, 1995). 
4. Redes de comunicaciones que soporten el tráfico de los 
paquetes transmitidos en tiempo real (Ferrari, 1992) 
(Chen y Cheng, 1997) (Rajkumar et al., 1997). 
5. Bases de datos en tiempo real (Abbott, 1991) (Huang y 
Stankovic, 1991). 
1.2.51.2.51.2.51.2.5 CCCCONCLUSIONESONCLUSIONESONCLUSIONESONCLUSIONES 
Es de destacar que existe una gran divergencia entre la 
investigación sobre movimiento en escenas y la orientada a 
arquitecturas para visión y seguimiento de objetos. Mientras que 
se han obtenido resultados prometedores usando las 
representaciones activas, empleándolas sobre plataformas 
computacionales de propósito general, apenas se han trasladado 
a arquitecturas más especializadas. 
Las arquitecturas están enfocadas, principalmente, al cálculo del 
flujo óptico y al seguimiento de características como son esquinas 
o aristas. Este hecho provoca que no existan apenas 
arquitecturas para el análisis de movimiento no-rígido general 
(elástico o fluido) que, como ya se comentó previamente, es el que 
más se da en la naturaleza. 
CAPÍTULO 1 
 
 
40
Difícilmente se encuentran arquitecturas de análisis del 
movimiento en las que los elementos de procesamiento guarden 
una relación topológica con la secuencia de imágenes. En esos 
casos, cada uno de dichos elementos suele realizar una operación 
diferente sobre toda o parte de la imagen. Prácticamente la única 
excepción es la de los computadores en rejilla, que representan el 
espacio n-dimensional donde se mueve el objeto mediante una 
malla de procesadores. 
Por último, la mayor parte de las arquitecturas específicas de 
visión están diseñadas para que operen con las fuertes 
restricciones temporales que vienen dadas por la frecuencia de 
video a la que hay que procesar la información, basándose, sobre 
todo, en hardware y software de altas prestaciones. Sin embargo, 
se echa en falta investigación orientada a hacer consideración de 
las restricciones temporales con mayor flexibilidad y potencia, 
como puede ser la obtención del resultado por refinamiento 
sucesivo. De hecho, el trabajo realizado en el desarrollo de 
arquitecturas de tiempo real no ha sido muy extendido, dejando 
el tratamiento de las restricciones temporales para niveles 
superiores. 
1.31.31.31.3 PPPPROPUESTA DE SOLUCIÓNROPUESTA DE SOLUCIÓNROPUESTA DE SOLUCIÓNROPUESTADE SOLUCIÓN 
Tomando la idea de las representaciones activas, se va a 
proponer un modelo de representación que adapte su topología 
(elementos de procesamiento y red de interconexión) a la forma y 
situación del objeto. La estructura de datos debe ser sencilla y 
rápida de obtener, de modo que sirva de base al desarrollo de 
arquitecturas de alto rendimiento. Por otro lado, si el proceso de 
adaptación es iterativo, se podrán obtener representaciones 
aproximadas de los objetos en función del tiempo disponible. A 
continuación, se presenta la propuesta de solución de 
construcción del modelo de representación. 
Dado un objeto que presenta unas características geométricas en 
cuanto a forma, posición,...; y una apariencia visual (color, tono 
de gris, brillo, saturación,...), el problema de representación del 
objeto va a consistir en la obtención de su apariencia geométrica 
a partir de su apariencia visual. 
INTRODUCCIÓN: OBJETIVOS Y ESTADO DEL ARTE 
 
 
41 
Para ello, dada una imagen, se realiza una transformación de la 
misma, extrayendo la probabilidad de cada uno de los puntos de 
pertenecer al objeto, basándose en el cumplimiento de una cierta 
propiedad visual. Empleando esta función de transformación 
como campo de potencial, se pretende que el modelo adapte su 
topología al espacio de entrada determinado por el objeto. Este es 
precisamente el comportamiento que tienen los modelos 
neuronales auto-organizativos, donde su aprendizaje está 
encaminado a la satisfacción de diversos objetivos (Fritzke, 1997), 
principalmente: minimización del error, maximización de la 
entropía, mapeado de características preservando su topología, 
estimación de la función de densidad de un conjunto de señales y 
división en clusters. 
Si el espacio de entrada viene determinado por los puntos de la 
imagen que pertenecen al objeto, estas redes permitirán 
representarlo, minimizando el error de cuantización de sus 
elementos de procesamiento y representando su geometría 
mediante su red de interconexión. Sin embargo, como los 
diferentes modelos auto-organizativos poseen diferente capacidad 
de preservar la topología, se realizará un estudio para establecer 
cual de ellos tiene un mejor funcionamiento. 
Se define el Grafo Preservador de la Topología C,AGPT = como 
el grafo cuyos nodos están situados en los puntos asociados a 
cada uno de los elementos de procesamiento, estableciendo una 
arista entre aquellos nodos cuyos elementos de procesamiento 
respectivos están conectados. Este grafo GPT realiza una 
representación aproximada de la apariencia geométrica del 
objeto. 
Por lo tanto, el problema de obtención de la apariencia geométrica 
del objeto, es el del cálculo de un Grafo Preservador de la 
Topología GPT que lo represente. Este grafo puede ser empleado 
como caracterizador de la forma del objeto, en procesos 
posteriores de reconocimiento y/o clasificación. Como la 
comparación entre grafos es muy costosa computacionalmente, 
debería ser sencilla la extracción de características a partir de 
éste, que permita mejorar los procesos de más alto nivel. 
Si las propiedades del objeto varían con el tiempo, se presentarán 
diferentes instancias del mismo, en sucesivas imágenes. Para 
CAPÍTULO 1 
 
 
42 
facilitar el problema, se suelen incluir ciertas restricciones para 
limitar la localización de un objeto o de alguna de sus partes 
entre imágenes consecutivas de una secuencia. Cédras y Shah 
(1995) establecen varias posibles limitaciones: uniformidad del 
movimiento, velocidad máxima, suavidad del movimiento o 
cambios pequeños en la velocidad, movimiento común, 
correspondencia consistente, rigidez,... Escolano (1997) agrupa 
todas éstas en dos: coherencia del movimiento y uniformidad del 
movimiento. 
De este modo, la arquitectura debe ser capaz de reconfigurar su 
topología, de manera que para cada instancia del objeto, se 
obtenga su representación correspondiente mediante un Grafo 
Preservador de la Topología. Dado el carácter dinámico de los 
modelos auto-organizativos, que no requieren comenzar el 
aprendizaje cuando se introducen nuevos patrones, el 
seguimiento de objetos va a consistir en la readaptación de la red 
en cada una de las imágenes. 
Por tanto, el problema del seguimiento de objetos se plantea como 
la readaptación de la arquitectura, de modo que represente en 
cada instante de tiempo la apariencia geométrica del objeto. 
Se plantean dos formas de reconocer el movimiento: 
• basado en el reconocimiento, 
• basado en el movimiento. 
Para el primero de ellos, se procede a reconocer cada una de las 
instancias del objeto, a partir de su GPT o a partir de 
características extraídas de éste. La secuencia de diferentes 
instancias del objeto reconocidas determina el movimiento 
realizado. 
Para un análisis basado en el movimiento, se extrae información 
sobre la dinámica que han seguido las diversas configuraciones 
de la arquitectura. Para ello, se obtiene información de las 
trayectorias seguidas por cada uno de los elementos de 
procesamiento, entendidas como la sucesión de puntos de la 
imagen asociados a cada uno de ellos. Dado que en todo 
momento se tiene localizado a cada uno de estos elementos de 
INTRODUCCIÓN: OBJETIVOS Y ESTADO DEL ARTE 
 
 
43 
procesamiento, se evita el problema de correspondencia, que es 
uno de los más costosos de resolver. 
El análisis del movimiento, por tanto, queda establecido por el 
estudio de las diferentes apariencias geométricas que toma el 
objeto, de modo que puede ser tratado desde dos puntos de vista: 
mediante el reconocimiento de cada una de las instancias del 
mismo, o mediante el estudio de la dinámica de readaptación de la 
arquitectura.