Desarrollo de arquitecturas para procesamiento de control de la mirada en sistemas de visión activa con resolución espacial variable
Abstract
En esta tesis se aborda la implementación de un sistema completo de visión activa, en el que se capturan y generan imágenes de resolución espacial variable. Todo el sistema se integra en un sólo dispositivo del tipo AP SoC (All Programmable System on Chip), lo que nos permite llevar a cabo el codiseño hardware-software del mismo, implementando en la parte lógica los bloques de preprocesado intensivo, y en la parte software los algoritmos de procesado de control más complejo. El objetivo es que, trabajando con un campo visual del orden de Megapíxeles, se pueda procesar una tasa moderada de imágenes por segundo. Las imágenes multiresolución se generan a partir de sensores de resolución uniforme con una latencia nula, lo que permite tener preparada la imagen de resolución variable en el mismo instante en que se ha terminado de capturar la imagen original. Como innovación con respecto a las primeras contribuciones relacionadas con esta Tesis, se procesan imágenes con toda la información de color. Esto implica la necesidad de diseñar conversores entre espacios de color distintos, para adecuar la información al tipo de procesado que se va a realizar con ella. Estos bloques se integran sin alterar la latencia de entrega de los sucesivos fotogramas. El procesamiento de estas imágenes multirresolución genera un mapa de saliencia que permite mover la fóvea hacía la región considerada como más relevante en la escena. El contenido de la imagen se estructura en una jerarquía de niveles de abstracción. A diferencia de otras arquitecturas de este tipo, como son la pirámide regular y el polígono foveal, en las que se trabaja con imágenes de resolución uniforme en los distintos niveles de la jerarquía, la pirámide irregular foveal que se propone en esta tesis combina las ideas de trabajar con una imagen realmente multirresolución, que incluya el campo de visión completo que abarcan sensor y óptica, con el procesamiento jerárquico propio de las pirámides irregulares. Para ello en esta tesis se propone la implementación de un algoritmo de diezmado irregular que, tomando como base la imagen multirresolución, dará como resultado una estructura piramidal donde los distintos niveles no son imágenes sino grafos orientados a la resolución del problema de segmentación y estimación de saliencia. Todo el sistema se integra en torno a la arquitectura de bus AXI, que permite conectar entre si todos los cores desarrollados en la parte lógica, así como el acceso a la memoria compartida con los algoritmos implementados en la parte software. Esto es posible gracias a los bloques de acceso directo a memoria AXI-VDMA, en una propuesta de configuración que permite tanto la integración perfectamente coordinada de la transferencia de la imagen multirresolución generada a la zona de trabajo del algoritmo de segmentación como su recuperación para la posterior visualización del resultado del proceso, y todo ello con una tasa de trabajo que mejora los resultados de plataformas similares.
Full text
Desarrollo de Arquitecturas para Procesamiento de Control de la Mirada en Sistemas de Visión Activa con Resolución Espacial Variable Tesis Doctoral Martín González García Escuela Técnica Superior de Ingeniería de Telecomunicación 2016 O b j ect 3O b j ect 3O b j ect 3O b j ect 3O b j ect 3O b j ect 3O b j ect 3O b j ect 3O b j ect 4O b j ect 4O b j ect 4O b j ect 4O b j ect 4O b j ect 4O b j ect 4O b j ect 4O b j ect 4
AUTOR: Martín González García http://orcid.org/0000-0002-9216-0372 EDITA: Publicaciones y Divulgación Científica. Universidad de Málaga Esta obra está bajo una licencia de Creative Commons Reconocimiento-NoComercial-SinObraDerivada 4.0 Internacional: Cualquier parte de esta obra se puede reproducir sin autorización pero con el reconocimiento y atribución de los autores. No se puede hacer uso comercial de la obra y no se puede alterar, transformar o hacer obras derivadas. http://creativecommons.org/licenses/by-nc-nd/4.0/legalcode Esta Tesis Doctoral está depositada en el Repositorio Institucional de la Universidad de Málaga (RIUMA): riuma.uma.es
Departamento de Tecnología Electrónica E.T.S.I. de Telecomunicación Universidad de Málaga Tesis Doctoral Desarrollo de Arquitecturas para Procesamiento de Control de la Mirada en Sistemas de Visión Activa con Resolución Espacial Variable Autor: Martín González García Ingeniero de Telecomunicación Director: Pelegrín Camacho Lozano Doctor Ingeniero de Telecomunicación
Resumen En esta Tesis se aborda la implementación de un sistema completo de visión activa, en el que se capturan y generan imágenes de resolución espacial variable. Todo el sistema se integra en un sólo dispositivo del tipo AP SoC (All Programmable System on Chip), lo que nos permite llevar a cabo el codiseño hardware-software del mismo, implementando en la parte lógica los bloques de preprocesado intensivo, y en la parte software los algoritmos de procesado de control más complejo. El objetivo es que, trabajando con un campo visual del orden de Megapíxeles, se pueda procesar una tasa moderada de imágenes por segundo. Las imágenes multiresolución se generan a partir de sensores de resolución uniforme con una latencia nula, lo que permite tener preparada la imagen de resolución variable en el mismo instante en que se ha terminado de capturar la imagen original. Como innovación con respecto a las primeras contribuciones relacionadas con esta Tesis, se procesan imágenes con toda la información de color. Esto implica la necesidad de diseñar conversores entre espacios de color distintos, para adecuar la información al tipo de procesado que se va a realizar con ella. Estos bloques se integran sin alterar la latencia de entrega de los sucesivos fotogramas. El procesamiento de estas imágenes multirresolución genera un mapa de saliencia que permite mover la fóvea hacía la región considerada como más relevante en la escena. El contenido de la imagen se estructura en una jerarquía de niveles de abstracción. A diferencia de otras arquitecturas de este tipo, como son la pirámide regular y el polígono foveal, en las que se trabaja con imágenes de resolución uniforme en los distintos niveles de la jerarquía, la pirámide irregular foveal que se propone en esta Tesis combina las ideas de trabajar con un imagen realmente multirresolución, que incluya el campo de visión completo que abarcan sensor y óptica, con el procesamiento jerárquico propio de las pirámides irregulares. Para ello en esta Tesis se propone la implementación de un algoritmo de diezmado irregular que, tomando como base la imagen multirresolución, dará como resultado una estructura piramidal donde los distintos niveles no son imágenes sino grafos orientados a la resolución del problema de segmentación y estimación de saliencia. Todo el sistema se integra en torno a la arquitectura de bus AXI, que permite conectar entre si todos los cores desarrollados en la parte lógica, así como el acceso a la memoria compartida con los algoritmos implementados en la parte software. Esto es posible gracias a los bloques de acceso directo a memoria AXI-VDMA, en una propuesta de configuración que permite tanto la integración perfectamente coordinada de la transferencia de la imagen multirresolución generada a la zona de trabajo del algoritmo de segmentación como su recuperación para la posterior visualización del resultado del proceso, y todo ello con una tasa de trabajo que mejora los resultados de plataformas similares.
Abstract This Thesis proposes the development of an active vision system, which is able to capture and generate space-variant images. All the system is endowed within a unique AP SoC (All Programmable System-on-chip), following the guidelines of the hardware-software codesign: those blocks in charge of the intensive preprocessing are synthesised on the logic part (hardware), meanwhile the algorithms that require a more complex control are programmed on the software part. The aim is that, working with a visual field of the order of megapixels, the whole system can process a moderate rate of images per second. Multiresolution images are generated from a CMOS sensor of large resolution with zero latency. This allows the system to provide the space-variant image when the capture of the original image ends. One of the novelties with respect to the first contributions related to this PhD Thesis is that images are processed considering all the colour information. This implies the design of converters able to translate between different colour spaces. Thus, we adapt the information to the type of processing that will be performed with her. These blocks are integrated within the architecture without altering the latency delivery of successive frames. The processing of these multiresolution images focuses on generating a saliency map. This map allows to continuously moving the fovea to the region considered the most relevant one in the scene. For obtaining the saliency map, the image content is structured into a hierarchy of levels of abstraction. Unlike other similar proposals, such as regular pyramids or foveal polygons, in which all levels of the hierarchy are encoded as images of uniform resolution, the irregular foveal pyramid proposed in this Thesis successfully combines the idea of working with a multiresolution image, which covers the visual field provided by sensor and optics, with the hierarchical processing coming from irregular pyramids. The result is a novel decimation scheme that deals with a hierarchy whose levels are encodes using simple graphs. The system is built around the AXI bus. It allows to connect all the cores development on the logic part of the AP SoC, and also that the algorithms running on its software part can access to the shared memory. This is possible thanks to the blocks of direct memory access AXI-VDMA, in an architectural proposal that permits both the perfectly coordinated integration of the transfer of the multiresolution images to the working area of the segmentation algorithm and its recovery for the rear display of the obtained results. And all this with a frame rate that improves the results obtained on similar platforms.
Figura 4-22: Diferentes retinotopologías en función de los valores de Ld, Rd, Td y Bd, para una estructura con dos anillos..................................................................................................107 Figura 4-23: El espacio de color HSV puede ser representado por un cilindro y el espacio RGB como un cubo..............................................................................................................................108 Figura 4-24: Diagrama de bloques de la distribución de los distintos procesos entre la parte PS y la parte PL del APSoC. A la DDR se accede desde el controlador asociado a la parte PS. 111 Figura 4-25: Segmentación del espacio de memoria para el procesado de los distintos frames.....112 Figura 4-26: Diagrama de secuencia asociado al proceso de segmentación...................................114 Figura 4-27: Diagrama de secuencia asociado al proceso de estimación de la saliencia y la posición del nuevo foco de atención................................................................................................115 Figura 4-28: Proceso de almacenamiento de los índices de la representación multirresolución para la estimación de los vecinos superior-inferior (ver texto)..................................................117 Figura 4-29: Diagrama de flujo del proceso de cálculo de los valores p y q asociados a los nodos de un grafo de la pirámide irregular foveal.............................................................................119 Figura 4-30: Diagrama de flujo del proceso de definición de enlaces intrae inter-nivel y caracterización de los nodos del nivel l+1 en la pirámide irregular foveal........................120 Figura 4-31: Generación de la pirámide irregular foveal para un ejemplo simple de retinotopología ...........................................................................................................................................121 Figura 4-32: Diagrama de flujo del programa de estimación de la saliencia.....................................122 Figura 5-1: Resultados de la reconstrucción por interpolación bilineal.............................................130 Figura 5-2: Esquema de obtención del mapa de bordes en el marco de comparación con las imágenes de la BSDB500.................................................................................................139 Figura 5-3: Imágenes de bordes resultantes del proceso de fovealizar con cinco fijaciones la imagen original (#161062 y #310007 de la base de datos BSDS500)..........................................139 Figura 5-4: (arriba) Imagen #310007 de la base de datos BSDS500 y versión fovealizada; y (abajo) segmentación e imagen de bordes resultante..................................................................141 Figura 5-5: Número de vecinos despreciados por nodo y nivel en pruebas de segmentación de 10 imágenes de 480 x 320 píxeles de la base de datos BSDS500. La franja roja muestra la variación en torno a la media, obtenida usando el promedio y la varianza en la distribución.........................................................................................................................142 Figura 5-6: Evaluación del algoritmo de segmentación modificando el valor de la distancia color. La evaluación se ha repetido con saltos en el umbral de 10 puntos. Los mejores resultados se obtuvieron para un valor umbral de 200.......................................................................143 Figura 5-7: Comparación de nuestra propuesta con otras aproximaciones. Las curvas que, de otros métodos, se muestran en la figura han sido descargadas de http://www.eecs.berkeley.edu/Research/Projects/CS/vision/grouping/ (Arbeláez et al., 2011)..................................................................................................................................144 Figura 5-8: Imagen #147091 de la BSDS500 y su segmentación, tanto por personas, como por los métodos propuestos por Felzenszwalb yHuttenlocher (2004), Comaniciu y Meer (2002), Arbeláez (2006), y Cour et al. (2005). Para cada método se muestran las mejores segmentaciones de acuerdo al valor de medida F............................................................145 Figura 5-9: Exploración activa de una secuencia de vídeo (izquierda) imágenes foveales, y (derecha) imágenes uniformes. En ambos casos los parámetros usados en las etapas del sistema son los mismos. En rojo se muestra la posición de la fóvea, mientras que en azul la posición a la que saltará en el siguiente fotograma......................................................147 Figura 5-10: Resultados de trayectorias de fijaciones para dos imágenes de la Toolbox Saliency: (izquierda) resultados obtenidos usando el método de Walther y Koch (2006), y (derecha) proto-objetos obtenidos usando el método propuesto. El orden seguido por las fijaciones se muestra sobre las imágenes.........................................................................................149 Figura 5-11: Exploración activa de la imagen #157055 de la BSDS500: desde la esquina superiorizquierda a la inferior-derecha, la figura muestra una secuencia de fijaciones................150 Figura 5-12: Trayectorias de fijaciones en la imagen #157055 de la BSDS500 usando el método propuesto por Walther y Koch (2006)................................................................................151 xvi
Figura 5-13: Evaluación de métodos usando la base de datos Toronto y el método del área bajo la curva ROC con eliminación del sesgo central (shuffled AUC). El método propuesto se marca en rojo entre el resto de aproximaciones (adaptación del original en Borji et al., 2013a)................................................................................................................................152 Figura 6-1: Entorno de trabajo en el proyecto FGACCESS: Zedboard y sensor Lince5M84...........159 xvii
Índice de tablas Tabla 3-1: Valor de la función Q, altura de la jerarquía y número de regiones para distintos esquemas de diezmado (ver texto).....................................................................................58 Tabla 4-1: Recursos de memoria disponibles en las últimas familias de FPGA de XILINX................82 Tabla 4-2: Diferentes configuraciones de memoria mediante la combinación de las 4 LUT disponibles dentro de un mismo SLICEM..............................................................................................83 Tabla 4-3: Posibles configuraciones de los bloques BRAM tanto en modos de funcionamiento como en la anchura de los buses de datos...................................................................................84 Tabla 4-4: Algunas directivas disponibles para controlar la generación de los distintos bloques de memoria durante el proceso de síntesis de alto nivel (HLS)..............................................86 Tabla 4-5: Características principales del sensor de Omnivision ov5642...........................................91 Tabla 4-6: Frecuencias de la señal de reloj de pixel (PCLK) en función de la resolución y el frame rate.......................................................................................................................................94 Tabla 4-7: Resumen de los nuevos CFA (Color Filter Array) propuestos comparados con el patrón Bayer como referencia........................................................................................................98 Tabla 5-1: Recursos utilizados por la implementación de la propuesta básica.................................126 Tabla 5-2: Comparación resultados con mejora en rendimiento y definición de interfaz..................127 Tabla 5-3: Comparativa resultados con ajuste de dimensiones y buffer de línea optimizado...........128 Tabla 5-4: Comparativa resultados con procesado particular en los bordes y con interpolación adaptativa frente a bilineal básica.....................................................................................129 Tabla 5-5: Resultados de síntesis de la propuesta básica para uno solo de los canales de color. Los recursos totales necesarios son los equivalentes a tres canales como el ilustrado en esta tabla...................................................................................................................................131 Tabla 5-6: Uso de los recursos BRAM con una anchura de datapath para unsigned short..............132 Tabla 5-7: Uso de los recursos BRAM con una anchura de datapath ajustada mediante el uso de tipos de precisión arbitraria en función de la etapa del datapath modelada.....................133 Tabla 5-8: Comparativa resultados con ajuste de datapath por uso de tipos arbitrarios y optimización del uso de los bloques BRAM mediante fusión de memorias...........................................134 Tabla 5-9: Comparativa resultados en función de la precisión en el tipo de datos de la aritmética en punto flotante, el uso de aritmética entera y la definición de la arquitectura pipeline......135 Tabla 5-10: Comparativa resultados en función de la precisión en el tipo de datos de la aritmética en punto flotante, el uso de aritmética entera y la definición de la arquitectura pipeline......136 xix
Capítulo 1 Introducción El término visión variante en el espacio aparece a finales de la década de los 80s para referirse a aquellas arquitecturas visuales que se basan en la variación, sobre el campo visual capturado, de la resolución de muestreo de datos. Son los también denominados sistemas de visión foveales, haciendo así referencia a la fóvea, la zona del ojo humano que captura la escena a máxima resolución. Asociados al desarrollo de soluciones que permitan percibir la escena usando cámaras y procesadores limitados, los sistemas de visión foveales se integrarán muchas veces con sistemas activos de control de la mirada y pares binoculares o cabezas robóticas (ver Figura 1.1). Es la época en la que se rompe con la denominada visión constructivista, asentada en los postulados de David Marr1, y en la que se sugiere que la percepción visual debe resolver el problema de describir escenas, para plantear que la visión debe servir, junto con otros sentidos, para interactuar con el entorno y sobrevivir en él - evitar obstáculos, reconocer y coger objetos…-. Es por ello la época de las cabezas binoculares o estéreo, los sistemas de control de la mirada, o los sensores de muestreo log-polar. También de los algoritmos jerárquicos de procesado visual, surgidos en muchos casos del mecenazgo de Azriel Rosenfeld y su Computer Vision Laboratory en la Universidad de Rutgers. Se plantea que el problema de la visión no debe tratar de resolverse 1‘The goal of an image-understanding system is to transform two-dimensional data into a description of the three-dimensional spatiotemporal world … must infer 3D surfaces, volumes, boundaries shadows, occlusion, depth…’ (J.K. Tsotsos, 1997, p. 389)
buscando que un modelado matemático permita obtener buenos resultados prácticos, sino que el proceso puede ser el contrario. Esto es, que la observación y el trabajo en cómo capturar la información permita la construcción de teorías exitosas. Es una propuesta precursora del embodiment, tan de boga en la robótica actual: el modelado matemático que, en la década de los 70s y principios de los 80s no había resuelto casos prácticos en visión, no podía desarrollarse ajeno ni al propio agente que percibe, y sus limitaciones hardware, ni tampoco a la tarea final a resolver (Aloimonos y Rosenfeld, 1991). Figura 1-1: La cabeza robótica binocular Popeye, diseñada en el marco de la visión activa en el Institute for Systems & Robotics, Universidad de Coimbra, Portugal Este marco, guiado en cualquier caso por una idea que, como escribe Peter Meer en 2001, era considerada en los años 60 como una tarea trivial: el diseño de un sistema genérico y autónomo de percepción visual, pierde fuerza conforme se entra en el nuevo siglo. El desarrollo de sensores foveales o sistemas de procesamiento jerárquico no parecen realmente necesarios ante la capacidad de procesamiento de los nuevos ordenadores personales, y se impone con rotundidad la necesidad de trabajar en soluciones muy acotadas por la aplicación, ahora en escenarios en los que las soluciones que surgen de la Estadística y el Cálculo probabilístico se imponen (como harán posteriormente en robótica (Thrun et al, 2005)). La posibilidad de nuevos sensores visuales de cada vez mayor tamaño y el advenimiento de las nuevas plataformas de sistemas en chip totalmente programables (AP SoC) abren nuevas posibilidades para el desarrollo de sistemas de captura variante en el espacio. Montadas sobre plataformas binoculares, estas nuevas arquitecturas pueden convertirse en una alternativa a las populares cámaras RGBD. 2
1.1. Objetivos de la Tesis El objetivo de esta Tesis es el diseño e implementación de un sistema de percepción visual sobre una plataforma AP SoC. Dicho sistema incluirá: •un módulo de adquisición de imagen foveal, que emulará el funcionamiento de un sensor de geometría cartesiano-exponencial de fóvea desplazable y tamaño variable; •un módulo de segmentación de imagen, que generará una jerarquía de niveles de abstracción creciente sobre los datos extraídos del sensor; y •un módulo de estimación de saliencia basado en descriptores obtenidos de las regiones en que se divide la imagen, que permitirá guiar la fóvea para englobar la región que se considere como más relevante. Los dos primeros módulos configuran la implementación de la que denominaremos pirámide irregular foveal, una propuesta de cambio en la organización horizontal de los datos de entrada a una pirámide irregular que, aprovechando la flexibilidad del grafo, supone que la base sea una imagen de resolución no uniforme. Esto rompe con la definición de pirámide como una jerarquía de niveles de resolución uniforme, pues los algoritmos de diezmado siempre aportarán más detalle a las zonas de cada nivel que se vayan generando sobre la fóvea. Todo el diseño se lleva a cabo para procesar el flujo de información a la mayor velocidad posible pero embebiendo la solución en un marco software-hardware plausible. Esto implicará abordar numerosos problemas y la toma de decisiones de diseño en los que se balanceará calidad, recursos hardware y tiempo de proceso. 1.2. Motivación Desde hace ya algún tiempo, la alta capacidad de integración de la tecnología CMOS ha permitido desarrollar e integrar una amplia gama de aplicaciones o sistemas en el mismo chip. Los denominados SoC (System on Chip) no sólo suponen un avance en lo que se refiere al hardware sino que además, al incorporar elementos de procesamiento para el desarrollo software, suponen un escenario distinto para el diseño y desarrollo de arquitecturas complejas, que requieren de las ventajas ofrecidas tanto por el hardware sintetizado como de la programación software. Por otra parte, no sólo los nuevos 3
microprocesadores empotrados siguen sacando provecho del desarrollo de la Ley de Moore, y su asociado aumento en la densidad de integración y potencia computacional, sino que ésta también afecta directamente al diseño de los sensores visuales, cada vez de mayor resolución. En este nicho surge el concepto de cámara inteligente, como un dispositivo que integra sensor y procesador empotrado para extender la capacidad típica de la cámara, la de capturar fotos o secuencias de vídeo, para que ahora sea capaz de procesar estos datos y así, incluso tomar decisiones en tiempo real. De esta forma, se puede entender que la cámara es capaz de trabajar a un medio o alto nivel, sirviendo la información relativa por ejemplo a la presencia de una persona o el seguimiento de un objeto en movimiento. El grupo de Ingeniería de Sistemas Integrados de la Universidad de Málaga tomará contacto con la temática de la visión activa en aquellos primeros años de los 90s, cuando la visita de César Bandera conducirá a nuestro grupo al restringido marco de las retinotopologías cartesiano-exponencial, la pirámide regular de Peter Burt o el polígono foveal. Fruto del trabajo en esa dirección serán las propuestas de desplazamiento de la fóvea en el campo de visión, la adaptación de su tamaño al objeto de interés o las poco explotadas retinotopologías multifoveales, propuestas en los sucesivos trabajos de Fabián Arrebola y Pelegrín Camacho. El procesamiento jerárquico será la base de la implementación a medida de la pirámide regular propuesta en la Tesis Doctoral de Francisco J. Coslado, pero también de la propuesta irregular presentada en la Tesis Doctoral de Rebeca Marfil. Aunque se habían esbozado propuestas en trabajos previos en el propio grupo, esta última Tesis propondrá también un mecanismo de atención que ha ido evolucionando hasta su versión más reciente, en el que se cierra el lazo percepción-acción incluyendo planificación automática, como se documenta en la Tesis Doctoral de Antonio J. Palomino. Los conceptos teóricos de sensado variante en el espacio, procesado jerárquico y mecanismo de atención forman parte, por tanto, del bagaje de nuestro grupo desde hace ya más de dos décadas. Pero además, en paralelo a este trabajo teórico, el grupo ha llevado a cabo un interesante recorrido en lo que se refiere al diseño de soluciones empotradas de visión artificial, basadas fundamentalmente en el empleo de dispositivos Field Programmable Gate Arrays (FPGA). En 2014 el grupo propone una primera arquitectura en la que se combinan sensado variante en el espacio, pirámides irregulares y mecanismos de atención, en un trabajo que se publica en la revista Frontiers (Marfil et al., 2014). Aprovechando parcialmente el trabajo previo a estas fechas en todos estos campos, pero con el ánimo de implementar una arquitectura completa y también novedosa sobre un AP SoC surge esta Tesis Doctoral, cuyo resultado 4
será una cámara inteligente, capaz de mover la fóvea de forma autónoma a aquella región que sea considerada por la cámara como más relevante. 1.3. Propuesta del sistema de visión foveal empotrado El esquema del sistema de visión foveal empotrado que se propone en la presente Tesis Doctoral se muestra en la Figura 1.2. El sistema incluye un sensor color de 5 Mpíxeles y un AP SoC, en el que se integrarán el hardware de captura de una imagen de fóvea desplazable y de tamaño optimizado y los algoritmos encargados de las segmentación de la imagen (usando un esquema de pirámide irregular) y de la evaluación de la saliencia para, en el marco general de un proceso de atención, poder determinar cuál es el objeto más relevante en la escena. En el esquema se ha incluido también la memoria externa, elemento básico para almacenar la enorme cantidad de datos con los que se trabaja. En la Figura 1.3 se muestran los elementos concretos con los que finalmente se llevarán a cabo las pruebas documentadas en esta Tesis: la placa Zedboard y su Zynq-7020 de Xilinx y el sensor OV5642 de Omnivision. Figura 1-2: Esquema general del sistema propuesto 5
ocurriendo con el resto de la escena, quizás a menor resolución, pero sí con el suficiente como para poder actuar en caso de necesidad. Frente a la visión central, que respondería a las habilidades de percepción en detalle hasta ahora comentadas, la denominada visión periférica es la habilidad de localizar, reconocer y responder a la información en las distintas áreas del campo visual alrededor del objeto sobre el cual se fija la atención. La retina periférica es especialmente sensible a los desplazamientos, siendo su función más característica la detección del movimiento, aunque también se ha constatado su utilización durante acciones de alcanzar y atrapar. También parece jugar un importante papel en la coordinación visuo-motora, la postura y locomoción en el espacio. Figura 2-1: Dependencia con la tarea del movimiento seguido por los ojos frente a una determinada imagen (Yarbus, 1967) En este Capítulo se describen las bases teóricas del diseño de una arquitectura de visión artificial que imita esta captura a distintas resoluciones de la imagen. En ocasiones, esta imitación tratará de acercarse al propio funcionamiento de nuestro sistema de visión. En otras, sin embargo, se alejará de éste por 12
razones de cómputo o eficiencia. Para ello, el Capítulo se organiza con una primera y muy breve introducción al sistema y proceso de visión humano (Sección 2.1). Después, en la Sección 2.2, se presentarán las aproximaciones artificiales a dicho sistema, no sólo en lo que respecta al sensor de captura, sino también a las primeras etapas del sistema de procesado de la información. En nuestro caso, el objetivo es implementar una arquitectura visual que permita el procesamiento jerárquico de una retinotopología foveal y en la que incluiremos un mecanismo artificial de atención. La novedosa arquitectura jerárquica propuesta en esta Tesis combina la captura de una imagen variante en el espacio con el concepto de jerarquía propio de las pirámides irregulares. La pirámide irregular foveal se introduce brevemente en la Sección 2.3, siendo su diseño e implementación descrito en el resto de Capítulos de esta Tesis. 2.1. El proceso de la visión humana Los ojos son como pequeñas cámaras digitales, que contienen lentes que enfocan la imagen sobre el globo ocular. Aunque muchos encuentren un problema el hecho de que, como muestra la Figura 2.2, la imagen capturada esté invertida en la parte posterior del ojo, hay que tener en cuenta que, en este símil, el cerebro es como un ordenador, aunque bastante diferente eso sí del digital basado en silicio, y para él es tan fácil trabajar con una imagen invertida como con una que no lo esté. Figura 2-2: Formación de la imagen en la retina Siguiendo con el símil, al igual que la cámara digital color tiene una matriz de elementos fotosensibles, que le permiten capturar la iluminación recibida a tres longitudes de onda distintas, el ojo humano tiene también una matriz de 13
receptores, los denominados conos, para capturar también tres colores distintos3. La analogía entre ambos sistemas va incluso más allá, pues al igual que las cámaras digitales comprimen la información antes de transmitirla o almacenarla, también la retina cuenta con varias capas de células que extraen lo que es más interesante de los datos capturados. Como resultado de este proceso, la información extraída de los más de 100 millones de receptores del ojo, puede ser transmitida al cerebro mediante el millón de fibras que, aproximadamente, forman el nervio óptico. En cualquier caso, ésta es sólo la primera etapa del sistema neuronal más complejo de todos nuestros sistemas sensoriales. Desde la retina, el eje óptico mueve la información al cerebro medio y el tálamo. Y desde esa zona el flujo de datos se mueve a la corteza visual primaria (Kandel et al., 2000). Existen, sin embargo, profundas diferencias entre ambos sistemas. Mientras que las cámaras digitales emplean mayoritariamente sensores de resolución uniforme, en los que los fotorreceptores se reparten en una matriz, la retina presenta una distribución no uniforme, en la que los fotorreceptores se concentran en una región central, la denominada fóvea. Además, en el caso del ojo no es totalmente correcto hablar de fotorreceptores, pues éstos son sólo una parte del sistema. En su conjunto, se puede entender que los hasta seis tipos distintos de células que forman las tres capas de la retina (bipolares, amacrinas, ganglionares… (Bouldac y Levine, 1997)) se organizan como pequeños procesadores de imagen (Purves et al, 2001). Como muestra la Figura 2.3, en nuestra retina únicamente una pequeña fracción de la escena, la recogida por la fóvea y los anillos adyacentes, es procesada a alta resolución espacial, mientras que la resolución con la que se procesa el resto de la escena, regiones intermedia y periférica, es bastante más baja. Esto es, el nivel de detalle con el que se capturan las imágenes no es constante a lo largo y ancho de campo de visión. De esta forma, la mitad de los recursos que el cerebro emplea en procesar la información visual sólo tratan con menos del 5% del campo visual percibido. Esto obliga a que el acto de percibir una escena implique el movimiento continuo de la fóvea, para que ésta incluya cada una de las zonas de interés en la misma. Dado que la estructura multirresolución de la retina es fija, este movimiento de la fóvea sólo puede ser llevado a cabo si se mueven los ojos. Esto es sumamente importante, y por ello el conjunto de músculos que mueven cada ojo (Figura 2.4) permiten que éste se desplace a unos 900 grados por segundo y entonces pararlo, todo en menos de una décima de segundo. Durante este instante de tiempo, conocido como movimiento sacádico, se suprime la visión. 3 Dejamos de lado los bastones, que principalmente trabajan sólo a niveles bajos de iluminación. 14
Así, aunque no seamos para nada conscientes de ello, percibimos el mundo a través de un conjunto de movimientos rápidos y fijaciones cortas. Controlar estos movimientos es evidentemente un aspecto clave del proceso de la visión en los seres humanos, que también es extensible a otros animales que, como los conejos, no presentan visión foveal. Figura 2-3: La distribución de los conos varía enormemente en la retina, dando lugar a brain pixels de tamaño variable, que se distribuyen siguiendo un modelo polar (adaptación del original de C. Ware, 2008, p. 5). Figura 2-4: Distribución de músculos encargados del movimiento del ojo 15
Resulta complejo diseñar un control realimentado tradicional para movimientos tan rápidos, pues esto requeriría usar ganancias altas y estimar con mucha precisión las derivadas que el modelo engloba. En suma, esto da lugar a controladores que fácilmente se vuelven inestables (Lesmana y Pai, 2011). Los estudios llevados a cabo tanto en humanos como en animales evidencian que el controlador empleado podría modelarse como un pulse-step no lineal (Collins, 1975). 2.2. Sistemas artificiales de visión con muestreo variable en el espacio El objetivo de los sistema artificiales de visión multirresolución es imitar el comportamiento no uniforme que presenta el sistema visual de algunos seres vivos. Este acercamiento se remonta a la década de los 70s, cuando ciertos investigadores en visión artificial deciden imitar la naturaleza foveal del sistema visual de los primates como una alternativa a los sensores de resolución uniforme convencionales. Y vendrá motivado, fundamentalmente, por los avances en la investigación de las propiedades espaciales del mapeo retinocortical en los mamíferos, especialmente en los primates, que se llevan a cabo desde la década de los 40s. En 1960 se demuestra que el desplazamiento de un estímulo de luz incidente en la retina de estos sistemas provoca, como respuesta, un desplazamiento en la información que llegaba a la corteza visual, y que este desplazamiento era inversamente proporcional a la distancia a la fóvea (Daniel y Whitteridge, 1961). Este efecto (cortical magnification) se traduce en un factor μc, medido en milímetros de corteza por grado de ángulo visual, que permitirá caracterizar la transformación o mapeo de los datos visuales desde las coordenadas en la retina a las de la corteza visual. Empíricamente, se encontró que dicho factor podía aproximarse por (Schwartz, 1977). μc(ρ)= C 1 1+C2ρ (2.1) donde ρ es la excentricidad en la retina, medida en grados, y C1 y C2 dos constantes que deben ser determinadas experimentalmente. Integrando esta ecuación, es posible establecer una relación entre la distancia cortical r y la excentricidad r(ρ)=∫0 ρ C 1 1+C2ρdρ= C 1 C2 log (1+C2ρ) (2.2) 16
Lo que permite observar el comportamiento general del mapeo retino-cortical, en el que el tamaño y distancia entre los campos receptivos asociados a cada célula ganglionar aumentaban linealmente con la excentricidad, esto es, con la distancia a la fóvea (Lindeberg y Florack, 1994). Además, también se completaron estudios que demostraban como estímulos lineales procedentes de la fóvea se organizaban aproximadamente a lo largo de líneas en la corteza visual, mientras que estímulos circulares centrados en la fóvea producían respuestas lineales en la corteza con orientaciones aproximadamente ortogonales (Tootell et al, 1982). Esto evidenciaba que el mapeo de la información que, transmitida desde la retina, llega a la corteza visual podía ser convenientemente expresado como una transformación conforme, esto es, como una función que presenta la propiedad de preservar los ángulos relativos4. En concreto, dicho mapeo podía modelarse, aproximadamente, siguiendo una ley logarítmico-polar (Schwartz, 1977). Esta será la base teórica del mapeo o transformación log-polar, sobre el cual volveremos en la Sección 2.2.1 del presente Capítulo. El paradigma de la visión activa surgirá en este marco a finales de la década de los 80s y principios de la de los 90s. No debe confundirse sin embargo con la visión foveal o multirresolución (space-variant), cuyas bases hemos introducido en los párrafos anteriores. La visión activa incide en la necesidad de mover el sensor, para así dirigir el campo de visión del mismo al objeto de interés. Surge en un momento en el que un fotograma de 512x512 píxeles de tamaño ya era considerado elevado, por lo que controlar un campo de visión grande a una resolución adecuada sólo podía hacerse en un tiempo razonable si el sensor, de una resolución reducida, se movía, recorriendo así la escena. En este contexto aparecen los mecanismos de atención y de control de la mirada, sobre los que volveremos en el Capítulo 3 de esta Tesis, pues ahora no se trata sólo de reconocer un elemento de la escena, sino también de saber cuál es el objeto o zona de la imagen que debe ser visitada. Se postula que esta capacidad de mover el sensor permitirá aportar soluciones más eficientes a problemas que, desde la perspectiva pasiva o reconstructivista, eran no lineales y estaban mal definidos (Aloimonos et al., 1988). Al esquema se unirá la posibilidad de manipulación que ofrecían los brazos y manos robóticas (Bajcsy, 1993; Swain y Stricker, 1993), o también la de crear campos visuales virtuales de alta resolución (Schwartz et al., 1995). En este contexto, al incorporar al sistema de visión activa un sensor foveal, normalmente log-polar, surgirá el concepto de visión activa variante en el espacio (space-variant active 4 Matemáticamente, una función ω=log(z), donde ω y z son variables complejas, es conforme en el punto z si es holomorfa (o antiholomorfa) en z y su derivada en z es distinta de cero. Una función se dice holomorfa en un punto z si su derivada existe en z y en todos los puntos vecinos a z 17
vision), en el que sí se unen visión activa y captura multirresolución (Schwartz et al., 1995). Como se ha descrito en el Capítulo 1 de esta Tesis, este es el marco en el que se encuadra la presente Tesis. A continuación se analizan en más detalle los dos modelos de transformación retino-cortical más empleados en visión artificial: el fundamentado en los trabajos introducidos en este apartado (el log-polar o log(z)) y el cartesiano. También se analizarán brevemente otras propuestas. Finalmente se analizarán los trabajos destinados a la fabricación específica de sensores no uniformes. 2.2.1. Transformación log-polar El mapeo log-polar es una transformación geométrica de la imagen que intenta emular la reorganización de la información visual que, como se ha comentado brevemente anteriormente, se produce en los primates al mover ésta desde la retina a la corteza visual. Como se ha introducido en el apartado anterior, conceptualmente, el modelo retino-cortical log(z) considera la retina como un plano complejo, en el que el centro de la fóvea corresponde al origen, y la corteza visual como otro plano complejo. Las posiciones en la retina se representan por la variable compleja z, y las posiciones en la corteza por la variable compleja Ω. La correspondencia entre los dos planos viene dictado por la función Ω = log(z). Dicha función presenta una singularidad en el origen (z = 0), lo que complicará la emulación o fabricación del sensor (Figura 2.5). Para eliminar el problema de la singularidad y fabricar un sensor físico, Giulio Sandini y su equipo introducirán dos mapeos distintos, uno para la fóvea -uniformey otro para la periferia -log-polar- (Sandini y Tagliasco, 1980; Braccini et al., 1981; Braccini et al., 1982). Ambos mapeos vienen dados por las ecuaciones {η=qθ ξ=loga ρ ρ0−ρ {η=qθjj∈[1,. .. Nang ] ξ=loga ρ1 ρ2i∈[1,... Ncir ] (2.3) donde (ρ,θ) son las coordenadas polares y (ξ,η) son las coordenadas log-polar. El valor ρ0 es el radio de la circunferencia que separa ambos mapeos. Los valores q y a son constantes que vendrán determinadas por el tamaño y forma del sensor, en aquel primer caso de tipo CCD. En concreto, 1/q determina la mínima resolución angular del layout log-polar. La Figura 2.6 muestra cómo quedaría el modelo. 18
Figura 2-5: El modelo log(z) para el mapeo retino-cortical. En el centro de la representación de la izquierda se muestra un pequeño círculo, que queda fuera del modelo para evitar el problema de singularidad de la transformación (Traver y Bernardino, 2009). El plano retinal de la izquierda se mapea en el plano cortical de la derecha usando w=log(z). Circunferencias concéntricas y líneas radiales en el plano de la retina se transforman en líneas rectas en el plano cortical. Figura 2-6: Transformación log-polar basada en dos mapeos distintos para la fóvea (uniforme) y la periferia (log-polar). Las imágenes de la derecha muestran la matriz de la fóvea en el plano cortical (arriba) y el de la periferia (abajo) (Bolduc y Levine, 1998) 19
En resumen, aunque la propuesta de usar dos modelos permitió en su momento la fabricación de un sensor real, la discontinuidad entre fóvea y periferia es una importante desventaja, que obliga a trabajar con dos mapas corticales distintos. Por ello, en paralelo al trabajo mencionado, Schwartz propuso eliminar el problema de la singularidad en el origen modificando la función que controla el mapeo, que sustituyó por la función log(z + a). Además, en sus trabajos de campo demostró que, seleccionando un valor adecuado para la constante a, era posible obtener un modelo aún más cercano al de primates o gatos que con la función log(z) (Schwartz, 1980). Figura 2-7: Transformación log-polar basada en la función log(z + a). La imagen de la izquierda muestra que el patrón es simétrico y elimina la singularidad en el origen, pero a costa de presentar sectores de anillos distintos en el eje y. La imagen de la derecha muestra la matriz en el plano cortical, con la característica forma de mariposa. En ella se ha marcado la posición del eje y (Bolduc y Levine, 1998) Como muestra la Figura 2.7 la matriz en el plano cortical no presenta una forma rectangular. El lado derecho se mapea usando ω = log(z + a), dando lugar a la parte derecha de la representación en el plano cortical, mientras que el izquierdo lo hace con la expresión ¯ ω= 2·log(a) - log(- ¯ z+ a), dando lugar a la parte izquierda de la matriz cortical. El mapeo en sí es conforme dentro de cada mitad del plano. Sin embargo, en un sentido matemáticamente estricto, las propiedades de invarianza en escala y rotación, que sí presenta la transformación log(z), se pierden5. Además, como el patrón se ‘pliega’ en el eje 5 Sin embargo, si se considera que |z|>>a, entonces log(z + a) ≈ log(z), y se puede considerar que las propiedades de invarianza se mantienen 20
y (ver Figura 2.7), los círculos concéntricos y centrados en la fóvea, o las líneas rectas que pasan por ésta, ya no mapean a líneas rectas en el plano cortical. 2.2.2. Transformación cartesiana exponencial El modelo cartesiano-exponencial aparece, a finales de los 80s, en las propuestas de César Bandera y Peter Scott (Bandera y Scott, 1989; Scott y Bandera, 1990; Bandera, 1994). Al igual que en la geometría log-polar, en este modelo la resolución disminuye al alejarnos del centro pero, a diferencia de la anterior, el campo receptivo de los ring sectors (o region pixels - rexels) es ahora cuadrado. Además, al alejarnos de la fóvea, el tamaño de éstos no cambia de forma continua, sino en saltos discretos, de forma que la relación de tamaño entre rexels de anillos consecutivos es una potencia de dos. En la Figura 2.8 se muestra una geometría cartesiana exponencial con una región periférica de tres anillos y fóvea. Se aprecia, sin embargo, que una línea que cruce desde el centro hasta el borde exterior de la cuadrícula atravesaría seis rexels. Cada anillo presenta un conjunto de subanillos de igual resolución. Así, la geometría de la Figura 2.8 se caracteriza por presentar tres anillos (m = 3) y dos subanillos (d = 2). Figura 2-8: Geometría cartesiana exponencial con m = 3 y d = 2 La geometría cartesiana no presenta discontinuidad entre la fóvea y la periferia, para lo que la fóvea debe presentar un tamaño de 4d x 4d. Además, al igual que la transformación log-polar, puede mapearse en la corteza asegurando que, líneas que pasen por la fóvea y cuadrados (no circunferencias) centrados en el origen, sean líneas rectas en el mapa cortical. La diferencia con respecto 21
La transformación exponencial dimensionalmente independiente (DIEM, Dimensionally-Independent Exponential Mapping) mapea de forma distinta a lo largo de los ejes vertical u horizontal (Peters y Arcot, 1998). La idea es simple: las muestras de la imagen uniforme que formarán parte de la retinotopología variante en el espacio se toman de la intersección de líneas horizontales y verticales. Como muestran los ejemplos de la Figura 2.17, la principal ventaja del DIEM es su flexibilidad, al permitir que los parámetros se puedan elegir para cada eje de forma independiente. Así, por ejemplo, es posible muestrear con más detalle cualquier parte del campo de visión. En cierta forma, estas ventajas las comparte con las GMFD optimizadas. Figura 2-17: DIEM: Ejemplos de muestreos variantes en el espacio 2.2.4. Sensores no uniformes En paralelo a la aparición de las propuestas biológicas y sus correspondientes desarrollos en el campo de las Ciencias de la Computación, la década de los 90s verá la aparición de sensores físicos cuyo diseño estará guiado por el paradigma de varianza en el espacio. Estos sensores buscan replicar, normalmente, la geometría de la transformación log-polar. El diseño de un sensor específico de geometría no uniforme implica, en primer lugar, elegir los dos parámetros que son condicionados por la tecnología: el tamaño mínimo de píxel y el tamaño máximo del sensor. Ambos determinarán, además, otro parámetro básico: el número total de píxeles del sensor. En el caso de las geometrías no uniformes, la relación entre este número y los dos parámetros citados no es directa, como sí lo es en el caso de un sensor uniforme. Para el caso de la geometría log-polar será además necesario fijar la relación entre los rexels de mayor y menor tamaño, que definiremos por la constante R (Sandini y Metta, 2002). 28
En la primera implementación que, usando tecnología Charged Coupled Device (CCD), se fabricó en el IMEC (Interuniversitary MicroElectronics Center) belga a propuesta de Giulio Sandini y su equipo (Van der Spiegel et al., 1989), el tamaño mínimo de píxel era de 30 μm x 30 μm, y el diámetro del sensor ocupó 9.4 mm. El sensor tenía 30 anillos, cada uno de los cuales disponía de 64 fotorreceptores. La fóvea se organizaba como una matriz regular de 102 píxeles (hay que recordar que éste era el esquema seguido por este grupo para evitar la singularidad de la transformación log-polar en el origen). En total el sensor cuenta con 2022 fotorreceptores. La Figura 2.18 (izquierda) muestra una imagen de dicho sensor, en la que se ha ampliado la zona de la fóvea y la transición con la región periférica. El valor de R estaba en 13.7, pues el rexel de mayor tamaño era de 412 μm x 412 μm. La tasa de adquisición estaba en los 50 fotogramas por segundo. Un tercer parámetro importante es la relación entre el tamaño del sensor y el del menor píxel (constante Q). El valor de este parámetro determina el tamaño de una imagen de resolución uniforme que tendrá el mismo campo de visión y la misma máxima resolución que su correspondiente sensor log-polar. Así, para el CCD descrito, Q es igual a 300. Esto es, si queremos emplear un sensor uniforme para replicar este sensor log-polar, éste deberá tener 300 x 300 píxeles. Las nuevas versiones de sensores log-polar usarán tecnología CMOS. En el marco del proyecto SVAVISCA6, el grupo de Giulio Sandini fabricará en Tower (Israel) un sensor de tamaño mínimo de píxel de 7 μm, usando tecnología CMOS de 0.35 μm. El conjunto de fotorreceptores en la periferia será de 252 x 110 = 27720, mientras que la fóvea será de 5473 píxeles. Las constantes R y Q serán ahora de 17 y 1100 respectivamente. El diámetro del sensor es de 7,1 mm. En el IMEC se fabricará una versión color de este sensor, usando patrones similares al conocido Bayer usado en sensores uniformes (Figura 2.19). En la Figura 2.18 (centro) se muestra el aspecto de otro sensor CMOS, el diseñado y fabricado por Robert Wodnicki y su equipo. Al igual que las soluciones propuestas por Sandini, el sensor presenta una fóvea uniforme rodeada por anillos de tamaño de fotorreceptor creciente. 6 http://www.lira.dist.unige.it/projects/logpolar/press.html 29
Figura 2-18: Sensores que imitan la retina: (izquierda) sensor CCD © 2002 IEEE (Van der Spiegel et al., 1989); (centro) sensor CMOS © 1995 IEEE (Wodnicki et al., 1995); y (derecha) sensor CMOS (Courtesy by Cypress Semiconductor Image Sensor) (Pardo et al., 1997) Como muestra la Figura 2.18 (izquierda), en el sensor CCD se ha dejado de fabricar toda una fila de rexels para poder dejar espacio a las conexiones que acceden a los fotorreceptores de las zonas foveal y periférica (señales de control y reloj). En los siguientes diseños CMOS (Ferrari et al, 1995; Pardo et al., 1997), fabricados por el consorcio formado por el IMEC y el IBIDEM, estas señales se trazan a través de canales radiales (Figura 2.20). Figura 2-19: Sensor CMOS color desarrollado en el IMEC en el marco del proyecto europeo SVAVISCA 30
Figura 2-20: Región central del sensor CMOS FUGA18 Aunque menos citado, el IMEC, en colaboración con Corticon Inc. y NSF, también desarrolló por esta misma época un sensor de distribución cartesiana para aplicaciones de seguimiento (Etienne-Cummings et al., 2000; van der Spiegel et al., 2002). El sensor, mostrado en la Figura 2.21, consta de una fóvea y un único anillo de resolución, y está diseñado para mantener un objeto determinado en la fóvea. Mientras el objeto puede ser capturado por la fóvea, el sistema manda órdenes a los motores para que lo muevan y mantengan el objeto centrado. Cuando el objeto sale de la fóvea, la estimación de su nuevo centroide recae sobre el procesado de la región periférica. Todo el procesamiento requerido para ello está integrado en el hardware del sensor. Figura 2-21: Microfotografía del chip para seguimiento desarrollado por Ralph EtienneCummings, Jan Van der Spiegel, Paul Mueller y Mao-zhu Zhang en Corticon Inc. 31
Finalmente comentar que, frente al desarrollo de sensores de geometría específica, las transformaciones log-polar o cartesiano-exponencial también se han obtenido usando dispositivos electrónicos dedicados que, en tiempo real, transforman la imagen uniforme del sensor para obtener la distribución deseada. En el caso de la geometría log-polar, estos trabajos son ligeramente anteriores al desarrollo de los sensores (Rojer y Schwartz, 1990; Weiman y Juday, 1990; Engel et al. 1994). En aquella época presentaban la ventaja de usar placas de desarrollo estándares, disponibles en el mercado a un precio razonable. Aunque como desventaja se esgrimió que estos sistemas estaban limitados por el tamaño del sensor uniforme (Sandini y Metta, 2002), es importante destacar que esta desventaja ya no existe hoy día, y es fácil encontrar sensores de 5MP a un precio muy razonable. Dada la evolución actual en dicho campo, es de prever que podamos emplear en nuestros prototipos, en los próximos años, sensores cercanos a los 20MP. En ese caso, no será difícil construir sensores de geometría no uniforme capturando los datos de los fotorreceptores ubicados en las posiciones que determine la transformación elegida. 2.3. La pirámide irregular foveal Como se describió en la Sección 2.1, la estructura de la retina humana no sólo comprende el conjunto de fotorreceptores, sino también un conjunto de células que, organizadas jerárquicamente, trabajan con esa información para responder al contraste, al movimiento o al color. Cada retina contiene aproximadamente 100 millones de fotorreceptores, varias decenas de millones de neuronas horizontales, bipolares y amacrinas, y aproximadamente sólo un millón de neuronas ganglionares (ver Figura 2.22). Sería pretencioso tratar de replicar esta estructura. Pero de ella podemos aprender varias lecciones. La primera y más importante es que la información visual debería ser tratada por un sistema realmente jerárquico: el cerebro no puede ser impresionado con toda la información capturada por los fotorreceptores pues difícilmente podrá trabajar con toda ella. Por otra parte, cada una de estas neuronas (ciertamente unas más que otras) comparte información con las neuronas de su nivel y la procesa y aporta al nivel superior. Este esquema, repetido en la corteza visual, será el germen de los algoritmos artificiales de procesamiento jerárquico que se presentan brevemente en el Apartado 2.3.1 y, en concreto, de la pirámide irregular foveal, estructura propuesta en esta Tesis y que se introduce en el Apartado 2.3.2. 32
Figura 2-22: Esquema destinado a mostrar los cauces separados al través de la retina del impulso recogido por conos y bastoncitos de los mamíferos. — a, bastoncitos; b, conos; e, células bipolares para bastón; f, células bipolares para conos; r, h, g, z, células gangliónicas (Cajal, 1891) (http://cvc.cervantes.es/ciencia/cajal/cajal_recuerdos/default.htm) 2.3.1. Algoritmos jerárquicos de procesamiento de imagen El principio general que se persigue con el procesamiento jerárquico en general fue concisamente descrito por Jean M. Jolion y Montanvert para el caso de la pirámide: ‘a global interpretation is obtained by a local evidence accumulation’ (Jolion y Montanvert, 1992). Para conseguir esta acumulación de evidencias locales, las estructuras jerárquicas representan el contenido de la imagen en distintos niveles de abstracción, que se pueden definir de forma general como grafos de nodos Vl conectados por un conjunto de arcos El. Estos arcos definen las relaciones horizontales en la estructura jerárquica y representan la vecindad de cada nodo en ese mismo nivel (arcos intra-nivel). Otro conjunto de arcos definen las relaciones verticales, conectando nodos entre niveles adyacentes de la pirámide (arcos inter-nivel). Este segundo conjunto de arcos establecen las relaciones de dependencia entre cada nodo del nivel l + 1 y un conjunto de nodos del nivel l (la denominada ventana de reducción). Comúnmente, los nodos que forman la ventana de reducción se denominan como los hijos del nodo que la define. El valor de este padre se calcula a partir de los valores de sus hijos usando una función de reducción, siendo el cociente entre el número de nodos del nivel l y el del nivel l + 1 el denominado factor de reducción. Usando este esquema, la acumulación de las evidencias locales se consigue con la sucesiva construcción del grafo Gl+1, asociado al nivel l + 1, desde el grafo asociado al nivel inferior Gl. Este proceso consta de tres pasos (Marfil et al., 2006): 33
1. Selección de los nodos del grafo Gl+1 entre los nodos de Vl. Este proceso de selección es un diezmado, en el que los nodos Vl+1 suelen nombrarse como nodos supervivientes. 2. Establecimiento de los enlaces inter-nivel. Cada nodo del grafo Gl se enlaza a un nodo en Gl+1, definiendo una partición en Vl. 3. Establecimiento de los enlaces intra-nivel. El conjunto de arcos El+1 se obtiene definiendo las relaciones de adyacencia entre los nodos Vl+1. Las relaciones padre-hijos definidas por la ventana de reducción se pueden extender hasta la base de la jerarquía. El conjunto de nodos de la base unidos a un nodo de cualquier de los niveles superiores forman su campo receptivo. La eficiencia de una estructura jerárquica para resolver una determinada aplicación (segmentación en regiones, detección de contornos, etc.) vendrá influenciada por dos características: la estructura de datos y el esquema de diezmado, definidas respectivamente por los enlaces intrae inter-nivel. La elección de una estructura de datos concreta determina la información que se puede codificar en cada nivel de la jerarquía. Define por tanto la red que forman los enlaces El+1, por lo que podemos decir que determinan las propiedades horizontales de la jerarquía. Por otra parte, el esquema de diezmado usado para construir cada nivel determinará la dinámica (altura, preservación de detalles, etc.) de la jerarquía reflejada en qué nodos sobreviven o cómo se enlazan los nodos de niveles consecutivos. Son las denominadas propiedades verticales. Teniendo en cuenta estas propiedades, las arquitecturas jerárquicas de procesamiento se han clasificado en regulares o irregulares. En las jerarquías regulares la estructura de datos es rígida, con relaciones intra-nivel fijas y el factor de reducción constante. Sólo las relaciones inter-nivel se pueden cambiar para adaptar la estructura jerárquica al contenido de la imagen. En general presentan la ventaja de que, al trabajar con una estructura de nivel inicialmente conocida, ésta suele definirse como una imagen, con lo que el software desarrollado para trabajar sobre ellas suele ser muy eficiente. Además, los arcos intra-nivel son fijos (en la imagen, las vecindades de cada píxel) y pueden codificarse eficientemente (en la imagen podrán extraerse directamente de la propia posición (x,y) del píxel). Sin embargo esta inflexibilidad también tiene sus desventajas: campos receptivos desconectados, gran variación en los resultados cuando la imagen de entrada se desplaza levemente, o incapacidad para representar, bien como región o bien como borde, entidades alargadas. Las pirámides irregulares presentan una estructura de datos más flexible, en la que cada nivel se representa como un grafo cuyo número de nodos vendrá determinado por el proceso de diezmado. Las 34
relaciones intere intra-nivel son ahora definidas en el proceso de construcción de la estructura completa. En general, desde un punto de vista siempre software, son computacionalmente más costosas, pese a las soluciones que se han buscado para mejorar este aspecto. Figura 2-23: Notación en estructuras jerárquicas 2.3.2. Procesamiento jerárquico de imágenes multirresolución Con frecuencia, las retinotopologías variantes en el espacio y las aproximaciones multirresolución se presentan como alternativas que compiten por la solución al problema del tratamiento de imágenes de gran tamaño. En parte, esta separación de las dos opciones surge del hecho de que no encontraremos fácilmente en la literatura la aplicación de un algoritmo jerárquico sobre la transformación log-polar, normalmente equiparada con muestreo variante en el espacio (podríamos citar el trabajo de Sumitha y Siebert (2006), en el que la jerarquía se emplea más para extraer características que para reorganizar el contenido de la imagen). Sin embargo, ese no es el caso de las geometrías cartesiano-exponenciales. Así, ya en su trabajo de 1989, César Bandera planteaba organizar el contenido 35
del mapeo cartesiano-exponencial como una estructura jerárquica, el denominado polígono foveal, en contraposición a la entonces popular pirámide (Jolion y Montanvert, 1992; Marfil et al., 2006). La Figura 2.24 muestra esquemáticamente cómo se organizan ambas estructuras. Como se trata de reflejar en la figura, el polígono presenta un número más reducido de procesadores que la pirámide, justificado en la diferencia entre sensar un campo de visión con un esquema uniforme o un esquema variante en el espacio. Esto propició que, en su versión regular (la única conocida hasta 2014), se haya implementado en hardware desde mediados de la década de los 90s (Du et al., 1995; Du et al., 1996). Figura 2-24: (izquierda) Esquema de la pirámide regular; y (derecha) el polígono foveal El polígono foveal está formado por niveles de resolución uniforme, en el que la fóvea ocupa la base o nivel inferior, y el resto de niveles combinan información que proviene del diezmado del nivel inferior (la zona más oscura en los niveles del polígono de la Figura 2.24 (derecha)) con rexeles de un determinado anillo de la geometría cartesiano-exponencial. En la cintura del polígono ya está representado todo el campo visual, al unirse el anillo más externo de la geometría cartesiano-exponencial al resultado del diezmado del nivel inferior. Sobre la cintura se construye una pirámide, que ahora trabaja ya con la información de todo el campo visual. El escenario en sí explica el distinto planteamiento con el que nacen geometrías log-polar y cartesiano-exponencial. En la primera se busca trabajar en el plano cortical, mientras que en la segunda la idea es más la de disponer de distintos niveles de abstracción con los que poder resolver distintas tareas (si se pretende reconocer objetos se trabajará con la fóvea, pero si se busca detectar movimiento (o flujo óptico como será el caso original de César Bandera) se trabaja ya sobre la cintura del polígono o, incluso, sobre niveles construidos sobre ésta). 36
Normalmente, el proceso de diezmado dentro del polígono foveal se ha llevado a cabo usando aproximaciones regulares. En aplicaciones de segmentación de imagen basadas en el nivel de gris, dicho diezmado se ha basado en la estrategia propuesta por Peter Burt en 1981 para la pirámide (Linked pyramid), adaptado para su empleo en el marco del polígono foveal (Arrebola et al., 1997; Coslado, 2004). En este proceso de diezmado, cada nivel del polígono foveal se puede considerar como una imagen que, a su vez, se diezma para formar una nueva imagen de menor tamaño o resolución. Se le añade entonces el nivel de resolución correspondiente, construyendo una imagen que puede ser de nuevo procesada. En parte, la obligación de tener que representar cada nivel como una imagen justifica la existencia de los niveles que aparecen bajo la cintura del polígono, niveles que, sin embargo, no se han llegado a emplear como entrada para ninguna tarea en especial. Los problemas que esta estrategia de diezmado presenta fueron publicados poco después de su propuesta por Peter Burt (Antonisse, 1982; Bister et al., 1990), y su uso sólo se justifica por la simplicidad que el manejo de imágenes, en las que la conectividad viene supuesta, puede aportar (Traver and Bernardino, 2010). Empleamos el término supuesta pues, si bien este esquema considera que dos píxeles vecinos en la imagen están realmente conectados en la imagen original, esto no tiene porqué ser realmente cierto. Como se ha comentado anteriormente, la superación de este error vendrá de la mano del empleo de las denominadas pirámides irregulares (Marfil et al., 2006). En el marco del polígono foveal, sólo recientemente se ha empleado una estrategia irregular para segmentar imágenes en color, en el que el proceso de diezmado se ha llevado a cabo usando la estrategia de la Pirámide Irregular Acotada (Bounded Irregular Pyramid, BIP) (Marfil et al., 2014). El esquema implica que las zonas internas a los anillos en la Figura 2.24(derecha) (así como la cintura del polígono y todos los niveles construidos sobre ésta) serán realmente grafos y no imágenes. Esto complica las estructuras empleadas, pero evita los problemas que presentan las aproximaciones regulares. Por tanto, podemos resumir que, como combinación de procesado jerárquico e imagen multirresolución, el polígono foveal constituye una propuesta interesante, justificada principalmente en el marco de un procesado regular, en el que cada nivel de la estructura es una imagen. Sin embargo, la estructura en sí también tiene desventajas. ¿Cómo trabajar sobre un campo visual realmente multirresolución? En el trabajo de José Martínez y Leopoldo Altamirano (2006) se documentan las dificultades que presenta trabajar sobre imágenes que sólo parcialmente cubren el campo de visión cuando se pretende implementar un algoritmo de seguimiento. Ejecutar dicha tarea sobre la cintura del polígono supone trabajar con una fóvea de baja resolución, tan reducida como la del 37
en el Capítulo 2 como arquitecturas de visión activa variante en el espacio (space-variant active vision) (Schwartz et al., 1995). Entendemos también que un mecanismo de atención que trabaje, no sobre representaciones de resolución uniforme, sino sobre representaciones en las que la cercanía a la fóvea te confiere mayor importancia, se asemejará más a la situación postulada en este mismo párrafo. Como se esbozó en el Apartado 2.3.3 y se analizará en la primera parte de este Capítulo (Sección 3.1), la pirámide irregular foveal cumple este requisito. Ya se ha repasado en el Capítulo 2 como la captura variante en el espacio del sistema de visión humano ha sido imitada artificialmente por distintas aproximaciones. De igual forma, la atención visual ha sido también estudiada en profundidad, provocando la propuesta de numerosos mecanismos artificiales (Frintrop et al., 2010). Sin embargo, la combinación de atención visual y captura foveal ha sido tratada sólo en limitadas ocasiones, en las que los autores han debido resolver cómo codificar la relación bidireccional entre la estimación de la saliencia visual y la segmentación de la imagen. Una relación normalmente basada en el concepto de objeto perceptivo o proto-objecto (Rensink, 2000), definido vagamente como la unidad de información visual que puede acotarse en una región coherente y estable, y que puede ser extraído de la imagen usando un algoritmo de segmentación perceptivo. El ciclo de trabajo de una arquitectura como las descritas implica, entonces, la segmentación de la imagen en regiones o proto-objetos, cuya saliencia o importancia será evaluada en el marco de un proceso de atención para así determinar a qué nuevo proto-objeto se dirigirá la fóvea. Parecería que es la estimación de saliencia la que depende de la segmentación, pero la relación entre saliencia y segmentación es, como se ha comentado, bidireccional. Para explicar esto volvamos al inicio del ciclo descrito, en el que se segmenta la imagen de entrada, y ahora lancemos el algoritmo de segmentación ¿qué parámetros seleccionar? La segmentación se define en la literatura como un problema abierto (ill-defined), pues se obtienen distintos resultados según los parámetros que se apliquen y, en muchas ocasiones, no existe forma de justificar cuáles son los correctos. El problema se muestra en la Figura 3.1, tomada del artículo de Ajay K. Mishra (2012), ¿qué segmentación de las dos mostradas es la correcta? Si estamos interesados en segmentar el caballo que aparece en la escena la solución correcta es la Figura 3.1 (derecha), pero si el objetivo son los árboles en el centro de la imagen, entonces diríamos que la correcta es la Figura 3.1 (centro). La evaluación de la importancia o saliencia es el resultado del mecanismo de atención visual. Así, en estas arquitecturas, una vez se ha estimado la saliencia de toda la imagen y se ha seleccionado una región de interés, la fóvea se mueve para encuadrarla. Esto obliga a capturar una imagen 44
foveal distinta, cuya segmentación devolverá un nuevo y distinto conjunto de proto-objetos. De esta forma, la última región de interés determina los parámetros de la segmentación, haciendo de ésta un proceso ahora sí correctamente definido (Mishra et al., 2012). Figura 3-1: Segmentación de una imagen natural en (centro) diez regiones, o (derecha) en sesenta regiones usando el algoritmo del corte normalizado (Imagen de Mishra et al. (2012)) El esquema descrito se muestra en la Figura 3.2. El módulo sombreado se describirá en el Capítulo 4 de esta Tesis, en el que se recogen aspectos más relacionados con la implementación final de todo el sistema en el AP SoC. El resto de módulos se describen en este Capítulo. La arquitectura en sí no está completa: el proto-objeto en la fóvea deberá ser analizado por aquellos componentes de más alto nivel que, condicionados por la tarea en curso, extraigan de él información semántica. Por otro lado, el sistema requiere de un módulo o sistema de inhibición de retorno (Marfil et al, 2014), que asegure que la fóvea no se localice continuamente sobre la misma región de interés. Figura 3-2: Esquema del modelo de atención foveal propuesto 45
El resto del Capítulo describe, en las Secciones 3.1 y 3.2 los procesos implementados para segmentar la imagen y para estimar la saliencia de cada región extraída. La Sección 3.3 presenta los resultados obtenidos al aplicar el esquema de atención visual completo en algunas secuencias de vídeo. Finalmente, en la Sección 3.4 se discuten los resultados obtenidos. 3.1. Segmentación multirresolución Como se comentó en el Apartado 2.3.3, la pirámide irregular foveal combina segmentación multirresolución y captura variante en el espacio. Para ello, sobre la imagen foveal se van acumulando niveles que combinan el procesado del nivel inferior, construyendo niveles de mayor abstracción. La construcción de un nivel a partir del inferior es, en sí mismo, un proceso de diezmado, esto es, un proceso de selección de nodos supervivientes, al que se une un proceso de agrupación. Ya se describió la diferencia entre diezmado regular o irregular en el Apartado 2.3.1. En esta Tesis se propone la implementación de un algoritmo de diezmado irregular, basado en el esquema de diezmado dirigido por los datos (D3P) propuesto por Jean Michel Jolion en 2003. Dicha implementación se sintetizará en las partes software y lógica de un dispositivo en chip (SoC) programable (AP SoC), para lo cual será necesario modificarlo como describiremos en el Apartado 3.1.2. Nombraremos esta implementación modificada como Bounded D3P, BD3P. La implementación final se describirá en el Capítulo 4. 3.1.1. El algoritmo D3P Como se describió en el Apartado 2.3.1, el gran problema de las pirámides regulares es que éstas no pueden adaptarse al contenido de la imagen debido a la rigidez de su arquitectura. Como respuesta a este problema surgen, en la década de los 90s, distintos modelos (Meer, 1989; Kropatsch et al., 1993), en los que cada nivel de la jerarquía es ahora un grafo en lugar de una imagen. Aparece el concepto de diezmado que hemos empleado anteriormente para referir cualquier proceso, regular o irregular, de generación de un nivel desde el inferior. Conceptualmente, sin embargo, el diezmado, como selección de un conjunto de nodos supervivientes de entre los nodos de un nivel, es siempre un proceso propio de estructuras irregulares. En las regulares es más frecuente que el nodo padre sea ya parte de la estructura, siendo los enlaces intra-nivel lo único que puede llegar a modificarse para adaptar la estructura al contenido de la imagen. 46
La primera propuesta de pirámide irregular fue descrita por Peter Meer en 1989. Básicamente la pirámide estocástica ya establece el proceso que definimos en el Apartado 2.3.1 de establecimiento de enlaces y selección de supervivientes. En 1992, dicho esquema será empleado en el caso práctico de la segmentación de imagen por Annick Montanvert y Jean Michel Jolion. Pese a ser la primera propuesta de procesamiento jerárquico adaptada a los datos, su éxito será muy limitado. El mecanismo de diezmado se aplica de forma iterativa sobre el conjunto de datos, en un proceso que debe hacer cumplir la regla de que el resultado del diezmado sea un conjunto independiente maximal del conjunto de nodos del nivel inferior. Esto hace que el proceso de generar cada nivel pueda ser lento y, además, el resultado pueda ser un grafo muy similar en tamaño al del nivel inferior. Para evitar estos problemas, Jean Michel Jolion propone en 2003 el proceso de diezmado dirigido por los datos (Data Driven Decimation Process, D3P). Sea G(l) = (N(l), E(l)) el grafo que representa el nivel l de la jerarquía, donde N(l) define el conjunto de nodos del grafo y E(l) el conjunto de arcos, y sea Vi la vecindad del nodo i definida como {j∈ V(l) : δij}, donde δij define el arco (i, j) ∈ E(l). Definida de esta forma, el nodo i no está incluido en su propia vecindad. Cada nodo i tiene asociado un valor xi mientras que los arcos no presentan valor alguno. El proceso de diezmado del D3P determina que un nodo i de G(l) sobrevive si y sólo si, es un máximo local o no tiene ningún vecino superviviente. Para implementar este proceso, cada nodo i se caracteriza usando dos nuevas variables binarias, pi y qi. La variable pi marca como 1 aquellos nodos que sobreviven. La variable qi por su parte, vale 1 en aquellos nodos que, no siendo máximos locales, tampoco tienen un máximo local en su vecindad. Los valores de ambas variables para todos los nodos de la base, pi(0) y qi(0), se fijan a 1. Para el resto de niveles se calculan siguiendo las ecuaciones pi(k+1) ⇔ (pi(k) OR qi(k)) AND xi > max ({xj : δij·qj(k)}) qi(k+1) = [~pi(k+1) AND ~pi(k+1) ∀∈ j Vi(k)] AND (Vi(k) ∅≠) Lo que implica un proceso ejecutado en dos fases, en la primera se evaluarían los pi(k+1) y en la segunda los qi(k+1). Cualquier nodo que, en esta segunda fase, tenga un valor qi(k+1) igual a 1 también sobrevive, por lo que su valor pi(k+1) se hace entonces igual a 1. El proceso no es iterativo y puede hacer que muchos nodos, vecinos o no, sobrevivan sin que sean máximos locales. La Figura 3.3 muestra un ejemplo de aplicación del proceso de diezmado sobre un grafo de 25 nodos, en los que se ha marcado el valor de la variable xi. En la Figura 3.3 (izquierda) se marcan los nodos supervivientes en rojo (máximos 47
locales) y en verde (no hay máximos locales en su vecindad). Se observa que sobreviven nodos vecinos, ninguno de los cuales es máximo local. Figura 3-3: (izquierda) Grafo original –en cada nodo se ha marcado el valor de la variable xi-; y (derecha) nodos supervivientes marcados en rojo (máximos locales) y verde. El proceso D3P se puede aplicar en una única iteración, con las dos fases descritas. En la primera fase se marcan los máximos locales con pi igual a 1 y qi igual a 0. En la segunda se evalúan sólo los nodos con qi igual a 1: aquellos que tienen un máximo local (pi igual a 1) en su vecindad se marcan con qi igual a 0. Los nodos con pi ó qi igual a 1 se marcan como supervivientes (pi igual a 1). Si este proceso permite obtener los nodos del nuevo grafo G(k+1), los arcos E(k+1) se estiman como E(k+1) ={ (i, j)∈N(k+1) x N(k+1): i ≠ j AND path(i, j) ≤ 3 } donde path(i, j) ⇔ = 1 δij(k) path(i, j) ⇔∃ = 2 y ∈ N(k):δiy(k) AND δyj(k) AND y ∉ N(k+1) path(i, j) ⇔∃ = 3 y, x∈ N(k):δiy(k) AND δyx(k) AND δxj(k)AND y ∉ N(k+1) AND x ∉ N(k+1) Se aprecia como el cálculo de los arcos del nuevo nivel es un proceso más complejo, algo típico en las estructuras irregulares, que el propio proceso de selección de los supervivientes. 48
3.1.2. El algoritmo BD3P El algoritmo D3P presenta dos importantes problemas para su implementación en un sistema empotrado. Por un lado, cada nodo puede tener tantos vecinos como estime la topología de la imagen. Este problema ya fue descrito en el trabajo original de Jean-Michel Jolion en 2003 y es común a las propuestas irregulares. Las soluciones no pasan por limitar estas vecindades sino por ordenarlas usando alguna estrategia, de forma que luego pueda decidirse con quién se debe enlazar cada nodo no superviviente. Por ejemplo, Yll Haxhimusa y Walter Kropatsch propondrán, en las distintas implementaciones de la pirámide de grafo dual, la ordenación de este espacio de enlaces inter-nivel como un árbol, que puede luego cortarse enlazando uno o dos nodos nosupervivientes con cada superviviente. El problema de la asignación dinámica de un número de vecinos a cada nodo en el grafo, relacionado con el trazado del mallado inter-nivel, se convierte en crítico si el grafo que representa cada nivel quiere implementarse en la parte lógica del AP SoC, pero es igualmente importante si se implementa en la parte software y se quieren acotar los tiempos de cómputo y la memoria de almacenamiento. El otro problema grave del D3P radica en la necesidad de calcular, para cada nodo, las distancias L2 y L3 (los path(i,j) iguales a 2 ó 3 que se describen al final del Apartado 3.1.1). Estas distancias complementan la vecindad (distancia L1) y obligarían a almacenar, para cada nodo, quienes son sus vecinos a esas distancias. Su cómputo es iterativo y costoso y su almacenamiento elevaría en exceso el conjunto de información asociado a cada nodo del grafo. El algoritmo BD3P (Bounded D3P) que se propone en esta Tesis aborda ambos problemas y proporciona una implementación más eficiente y rápida del esquema de diezmado D3P, acotando la vecindad de cada nodo usando el marco de aplicación final y eliminando la necesidad de almacenar los vecinos a distancias L2 y L3. 3.1.2.1. Acotación del número de vecinos En su implementación en la parte lógica programable de un AP SoC, cada nodo del grafo necesitará almacenar el valor de todos sus vecinos. Al desconocerse inicialmente el número de vecinos, éste deberá ser asignado dinámicamente. Esta asignación dinámica, realizada en tiempo de ejecución, básica en el manejo de la memoria en programación, resulta un problema serio en nuestro caso. El problema de la asignación dinámica de recursos en hardware ha sido resuelto mediante la creación de bloques hardware de Asignación o Desasignación de memoria (Karabiber et al., 2007). En general, la asignación de bloques de tamaño fijo, que funciona bien en sistemas empotrados muy 49
simples, no es útil en estos casos, por lo que se suele recurrir al uso de algoritmos buddy. Básicamente, un asignador buddy gestiona la memoria desde un gran bloque, que suele ser tamaño potencia de dos. Si lo necesario es menor del doble que el tamaño del bloque, éste se parte en dos y el proceso de comparación se repite. El proceso se itera hasta que el bloque se ajuste al necesitado. Esto genera una estructura en árbol, en la que se encajan los bloques de distinto tamaño. Cada rama del árbol se marca con un bit, de forma que al asignar un bloque y poner el bit correspondiente a valor 1, las ramas que cuelguen desde este bloque ya no pueden asignarse. La desasignación consiste en marcar con un valor 0 el bloque ocupado. Esta estrategia ha sido empleada en la implementación de unidades hardware empotradas en diseños SoC. Así, el algoritmo de manejo activo de memoria (Active Memory Management algorithm, AMMU) se basa en una modificación del algoritmo buddy (Agun y Chang, 2001), en la que se propone el manejo con puertas OR de este árbol de asignación. Es un método fácil de integrar, pero que requiere unas cantidades elevadas de memoria para almacenar los mapas de bits, proporcionales al número de objetos o su tamaño. El algoritmo FEMA, propuesto por Karabiber et al. (2007), se presenta como una alternativa más eficiente, pero igualmente resulta costosa. La Figura 3.4 muestra el diagrama de bloques del algoritmo FEMA. El esquema necesita la implementación de la estructura lógica del árbol de puertas OR, el bloque de búsqueda de espacio libre y el de detección de espacio libre. 50
Figura 3-4: Esquema del algoritmo FEMA de asignación dinámica de memoria 51
Para evitar el consumo de todos estos recursos, se puede optar por asignar un tamaño fijo al vector de vecinos. En la gráfica de la Figura 3.5 se muestra el número de vecinos por nodo y nivel al aplicar el algoritmo D3P a imágenes naturales de tamaño 128 x 128 píxeles, tomadas de la base de datos BSDS500 (Martin et al, 2004). No se aplica ningún factor umbral, por lo que el proceso de agrupamiento termina por agrupar todos los píxeles de la imagen en una única clase. Los datos mostrados están adquiridos del procesamiento de más de 15Mpíxeles. En la gráfica se muestra una franja roja por nivel, obtenida usando el promedio del número de vecinos por nodo y la varianza total de la distribución. Se aprecia como la altura máxima de las pirámides generadas es de seis niveles. También como, en la base, prácticamente todos los nodos tienen ocho vecinos. También que, a partir del nivel 1, el número de vecinos por nodo disminuye. En el nivel 6 prácticamente quedan dos o tres regiones. Observando los resultados parece difícil determinar un valor exacto para el número de vecinos, incluso aunque éste se fije de forma independiente para cada nivel. Es importante además notar que, en una estructura irregular como ésta, el número de niveles es inicialmente desconocido. En función de la topología de la propia imagen, la estructura, con una base de igual tamaño, puede crecer más o menos. Sin embargo, podemos seguir preguntándonos si podemos fijar unos valores máximos. Para ello habrá que analizar más en profundidad el contexto completo, incluyendo la aplicación. Figura 3-5: Número de vecinos por nodo y nivel en pruebas de segmentación de 1000 imágenes de 128 x 128 píxeles. La franja roja muestra la variación en torno a la media, obtenida usando el promedio y la varianza en la distribución (estas imágenes son recortes de imágenes de la base de datos BSDS500) 52
3.1.2.2. Proceso de diezmado dirigido por la tarea En su trabajo original de 2003, J.M. Jolion no tiene en cuenta la aplicación final del proceso de diezmado sino su desarrollo teórico. Si nos movemos al campo de una aplicación concreta, en nuestro caso la segmentación de una imagen color, se puede entender que, en el conjunto de vecinos de cada nodo x, existirá un subconjunto de nodos que nunca se agruparán en la misma ventana de reducción que x al tener un color muy distinto. O si lo expresamos al revés, un subconjunto de nodos que posiblemente terminen por estar en la misma ventana de reducción que x al tener un color muy similar. Ambas afirmaciones, completamente subjetivas, implicarían que es posible limitar el conjunto de vecinos del nodo x a un valor específico. Incluso que dicha limitación puede ser beneficiosa pues, una vez que una conexión, un arco, no se establece entre dos nodos, se está disminuyendo la posibilidad de que ambos formen parte de la misma ventana de reducción. Si por color su fusión no es interesante, al dejar de introducir estos arcos en la estructura se estará potenciando la segmentación de la imagen en un conjunto de clases más limpio. El caso se esquematiza en la Figura 3.6. En la figura de la izquierda, el D3P asocia como vecinos, a todos los nodos del nivel inferior, aquellos que lo son por estar en contacto. Al generar el nivel superior, los dos nodos (rojo y azul) de valor x igual a 0.9 sobreviven, y el nodo azul de valor 0.6 sobrevive al no tener ningún vecino que sobreviva. Al trazar los enlaces inter-nivel, el nodo azul de valor 0.6 situado más a la izquierda sólo es vecino del nodo superviviente rojo, y deberá por tanto enlazarse a éste, degradando el valor de la región asociada a ese padre. El resto de enlaces inter-nivel son correctos. En la figura de la derecha, sin embargo, en el nivel inferior sólo algunos enlaces intra-nivel son válidos, aquellos que se han marcado en trazo más grueso. Ahora, al seleccionar los supervivientes, el nodo azul de valor 0.8 también sobrevive al ser un máximo local (no está conectado al nodo rojo de valor 0.9). Los nodos no supervivientes encuentran ahora vecinos de color correcto en su vecindad y los enlaces son todos correctos. Al plantear acotar el número de vecinos, el método se ha denominado Bounded D3P, BD3P. Es importante notar que, junto a la restricción impuesta de similitud en color, también impondremos una restricción de número máximo de vecinos. Esto facilitará la posible implementación en la parte lógica del SoC, pero también mejorará la velocidad de procesado si se ejecuta en la parte software. La primera restricción de distancia en color ayudará a no alcanzar este límite máximo y mejorará el resultado de la segmentación. Las ventajas que sólo se esbozan cualitativamente en la Figura 3.6 se aprecian más claramente en los resultados de segmentación que se presentan en la Figura 3.7. En concreto, en esta Figura 3.7 se ha limitado el número de vecinos a 20. La evaluación de resultados se analiza en más detalle 53
tamaño muy reducido, que aparecerán normalmente en la fóvea o cerca de ella. No se ha implementado un módulo de detección de movimiento o flujo óptico de bajo nivel. Es por ello que el movimiento ha sido inicialmente descartado. Aunque el contraste en intensidad no es considerado un atributo indispensable, esta característica ha sido incluida en nuestro esquema como un caso especial de contraste color (la intensidad aborda el caso de los valores grises, incluido el blanco o el negro). Además, hemos añadido una característica más relacionada con la forma del proto-objeto: la redondez, parámetro típicamente propuesto como representativo de auténticos objetos. La saliencia final de un proto-objeto, sali, vendrá finalmente determinado por la suma ponderada de estas características sali= λ· f donde λ es el conjunto de pesos, normalizados para que su suma sea la unidad, y f es el vector de características, que calcularemos como se describe en las siguientes subsecciones. Como se propone en la reciente Tesis Doctoral de Antonio J. Palomino (2014), estos pesos pueden adaptarse a la tarea en curso, aumentando la saliencia de los proto-objetos o regiones de la escena que puedan ser de mayor interés para resolverla. 3.2.1. Influencia en los cálculos del procesado multirresolución En los siguientes apartados se describirá cómo se calculan las características que determinan la atención. En las fórmulas que determinan estas características se usan perímetros, medias o momentos. Antes de presentar esas fórmulas hay que precisar cómo influye en su cómputo el hecho de tratar con una imagen multirresolución. El problema se describe en la Figura 3.9, en la que se ha marcado en azul una posible región, repartida entre distintos anillos de resolución. El perímetro de la región, o la longitud del mismo que ésta comparte con las cuatro regiones que la rodean, no puede calcularse sumando cuántos píxeles hay en el borde de la región, pues ahora la región se caracteriza por réxeles de distintos tamaños. En el ejemplo de la figura, la región azul presenta un perímetro bi bi= 5·L+ 7·L/2+4·L/4 que dependerá del distinto tamaño de los réxeles (en este caso, L es el tamaño del mayor de los réxeles que forman parte de la región), cuestión que habrá que tener en cuenta al establecer quiénes son los vecinos de la región. Además, como el algoritmo BD3P no almacena toda la vecindad del nodo, sino 60
sólo aquellos que son similares en color, habrá que mantener una doble estructura de almacenamiento en memoria para guardar esta información. Figura 3-9: La región en la imagen multirresolución podrá estar formada por réxeles de distintos tamaños. Eso influirá en los cálculos de perímetros, momentos o medias (ver texto). En el caso del cálculo del centroide o centro de masas de la región, habrá también que tener en cuenta el distinto peso de cada uno de los réxeles que componen la región. Esto es (¯ x,¯ y)= 1 ∑iwi ∑iwi(xi,y i) donde wi es el valor que determina el peso de cada rexel (xi ,yi) y vendrá dado por el área del mismo. El valor (xi ,yi) deberá ser el centro de masas del rexel. Finalmente, también el cálculo de cualquier momento deberá venir ponderado por este peso. Por ejemplo, para el momento μ1,1 μ1,1=∑iwi(xi−¯ x)( yi−¯ y) 61
3.2.2. Contraste color y contraste intensidad Los contrastes color e intensidad miden como de diferente es un proto-objeto de las regiones que lo rodean en la imagen en lo que se refiere a color e intensidad (luminosidad). Al formar parte de la teoría de atención de Anne Treisman y Garry Gelade, estas características han sido empleadas en los sistemas artificiales de atención desde los primeros modelos computacionales (Itti et al., 1998). Dado que los proto-objetos son el resultado de un proceso de segmentación perceptivo, el contraste color (ColCON) de un proto-objeto específico se puede calcular como la media del gradiente de color evaluado a lo largo de toda la periferia del proto-objeto. Para acelerar el cálculo y reducir la complejidad de su cómputo, dicho gradiente se calcula usando el color medio de las regiones: ColCONi= S i bi∑j∈Ni bij ·disColor (Ci,Cj) donde bi es el perímetro del proto-objeto Pi, Ni es el conjunto de proto-objetos que son vecinos de Pi, bij es la longitud del perímetro de Pi en contacto con el proto-objeto Pj, disColor(Ci,Cj) es la distancia color HSV entre los valores medios de color de los proto-objetos Pi y Pj; y Si es el valor medio de saturación del proto-objeto Pi. Para evitar el cálculo intermedio de los contactos entre proto-objectos y los correspondientes bij, el proceso de cálculo del contraste color se lleva a cabo no atendiendo a regiones, sino a réxeles. Eso permite calcularlo recorriendo sólo los réxeles del proto-objeto ColCON i=Si bi∑ j∈Mi ∑ k∈Nj∧k∉Mi bjk ·disColor(Cj,Ck) donde Mi define el conjunto de réxeles que forman al proto-objeto Pi, y Nj al conjunto de vecinos del rexel j. Los valores de bjk serán la longitud del lado del rexel, como se muestra en la Figura 3.9, un valor conocido. El valor de color del rexel, Cj, coincide con el del proto-objeto Pi. Debido al uso de Si en la ecuación de contraste color, los proto-objetos de color blanco, negro o gris no son tenidos en cuenta (su contraste color es siempre pequeño). Por ello se ha introducido una medida específica del contraste en intensidad. El contraste en intensidad (IntCON), de un proto-objeto, Pi, se calcula como el gradiente de valores medios de intensidad calculados a lo largo de su borde: 62
IntCON i=1 bi∑j∈Ni bij · disBrillo(Ii,Ij) donde Ii es el valor medio de luminosidad del proto-objeto. Al igual que con el contraste color, esta fórmula se ha modificado en la práctica para trabajar con los réxeles que forman el proto-objeto. Como resultado de este proceso se obtienen dos mapas de evidencias basados en el concepto de contraste, donde aquellos proto-objetos que difieren más en color, o intensidad, con las regiones que la rodean se marcan como más relevantes. Figura 3-10: Ejemplo de cálculo de las características de contraste color: (izquierda) imágenes originales (1920 x 1024 píxeles); y (derecha) mapa de evidencias asociado al contraste color. La fóvea en ambas imágenes se ubica usando T=B=7, L=8 y R=20. La Figura 3.10 muestra dos ejemplo de mapas de evidencia de contraste color. En la figura superior, sólo una de las regiones presenta una tonalidad distinta a la dominante, situación que es correctamente detectada por esta característica, como se muestra en el mapa de evidencia. En la figura inferior, sin embargo, hay una segunda región con una tonalidad distinta a la mayoría. Esta región, que presenta un color blanco, no es detectada correctamente por la medida de contraste color. 63
Figura 3-11: Ejemplo de cálculo de las características de contraste intensidad: (izquierda) imágenes originales (1920 x 1024 píxeles); y (derecha) mapas de evidencias asociado al contraste intensidad. La fóvea se ubica en ambas imágenes usando T=B=7, L=8 y R=20. El problema que ilustra la Figura 3.10 se soluciona con el contraste en intensidad. La Figura 3.11 muestra los mapas de evidencias asociados al contraste en intensidad para las dos imágenes de entrada empleadas como ejemplo en la Figura 3.10. La región blanca no es la más relevante en la imagen inferior pues alguna de las regiones que la rodean presentan también valores claros, pero se puede apreciar como ahora no es la tonalidad la que determina la saliencia sino el brillo (la mayoría de las regiones más salientes son regiones oscuras, en unas imágenes mayoritariamente claras). 3.2.3. Redondez La medida en redondez refleja lo parecido a un círculo que es el proto-objeto. Esta característica proporciona información sobre la convexidad, cierre y dispersión del proto-objeto. La redondez se obtiene empleando la clásica técnica basada en los momentos. En concreto se usan tres momentos centrales diferentes: μ1,1 i=∑iwi(xi−¯ x)( yi−¯ y)∀(xi,y i)∈Pi 64 μ2,0 i=∑iwi(xi−¯ x)2∀(xi,y i)∈Pi
donde ( ¯ x , ¯ y)es el centro del proto-objeto Pi. Combinando las ecuaciones anteriores es posible medir la diferencia entre una región determinada y un círculo perfecto. La medida, conocida como excentricidad, se calcula como ecci=(μ2,0 i−μ0,2 i)2+(2·μ1,1 i)2 (μ2,0 i+μ0,2 i)2 estando el resultado acotado al intervalo [0 . . . 1]. Finalmente, la redondez (ROUNDi) de un proto-objeto se obtiene a partir de la excentricidad usando la ecuación: R OUNDi=1−ecci La Figura 3.12 muestra un ejemplo del mapa de evidencias asociado a esta característica. Los mapas de saliencia que se muestran en la figura muestran que el proceso de fovealización distorsiona la forma de aquellas regiones que están en la zona periférica pero que, aún así, los círculos y cuadrados en la imagen obtienen los valores de saliencia más altos (mostrados en la figura como tonos más claros). Las formas más alargadas muestran valores menores de saliencia. La figura muestra los mapas de saliencia tras dos sacádicos, que han movido la fóvea, primero, al cuadrado verde, y después al círculo azul. Éste no tiene el valor máximo de saliencia en primera instancia debido a la distorsión que sufre su forma en la primera fovealización. 3.2.4. Orientación Como se comentó al comienzo de la Sección 3.2, la orientación es una de las fuentes de información que debe incluirse en el cálculo de la atención según Jeremy Wolfe. La orientación de una región en la imagen puede también calcularse usando los momentos centrales anteriormente descritos: ϕi=1 2arctan ( 2μ1,1 i μ2,0 i−μ0,2 i ) 65 μ0,2 i=∑iwi(yi−¯ y)2∀(xi,yi)∈Pi
Figura 3-12: Ejemplo de cálculo de la característica de redondez: (arriba) imagen original de 1920 x 1024 píxeles; y (abajo) mapas de evidencias asociados a la redondez de la regiones tras mover la fóvea por dos veces al proto-objeto más relevante. Los proto-objetos más relevantes se muestran en tono más brillante. En la primera fovealización, los parámetros de la GMFD de tamaño adaptativo son T=B=7, L=8 y R=20. En la segunda, la fóvea se desplaza al proto-objeto más relevante: el cuadrado verde dentro del azul. En la tercera al círculo azul. Estas segunda y tercera fovealización generan los mapas de evidencias que se muestran en esta figura. Pero la orientación de un proto-objeto, en sí misma, no proporciona ninguna información práctica sobre su relevancia. Sólo cuando se compara la orientación de un proto-objeto con la del resto de proto-objetos en la imagen se puede obtener una medida de relevancia. Por todo ello, es más interesante calcular la saliencia en términos de contraste. El contraste en orientación (OriCONi) de un proto-objeto se obtiene usando la ecuación: OriCONi=∑ j |ϕi−ϕj| donde j es el conjunto de proto-objetos en la imagen. La Figura 3.13 muestra un ejemplo del cálculo de la característica contraste en orientación. La mayoría de los objetos están orientados en una determinada 66
dirección, excepto uno de los rectángulos, que presenta una orientación distinta. El primer mapa que se muestra en la figura representa los valores de saliencia cuando la fóvea se ubica en una posición aleatoria, sobre uno de los rectángulos orientados en la dirección mayoritaria. Este mapa ya muestra como el proto-objeto más relevante es el que se orienta en una dirección distinta a la mayoría. El siguiente mapa muestra los valores de saliencia cuando la fóvea se ubica sobre este proto-objeto. La relevancia de esta región, en lo que a contraste en orientación se refiere, aumenta incluso respecto a los valores obtenidos en el mapa anterior. Figura 3-13: Ejemplo de cálculo de la característica de contraste en orientación: (arriba) imagen original de 1920 x 1024 píxeles; y (b) ; y (abajo) mapas de evidencias asociados al contraste en orientación de la regiones tras mover la fóvea desde una posición aleatoria al proto-objeto más relevante. Los proto-objetos más relevantes se muestran en tono más brillante. En la primera fovealización, los parámetros de la GMFD de tamaño adaptativo son T=B=7, L=8 y R=20. En la segunda, la fóvea se desplaza al proto-objeto más relevante: el rectángulo verde con distinta orientación. 3.2.5. Evaluación del mecanismo de atención El mecanismo de atención ha sido evaluado usando la base de datos Toronto (Bruce y Tsotsos, 2009), definida como la más empleada en el buen artículo de revisión de la materia de Ali Borji y Laurent Itti (2013b). La base de datos contiene 120 imágenes de 681 x 511 píxeles, con información de seguimiento 67
de ojos de veinte personas. Estas personas vieron la imagen durante cuatro segundos, sin que se le especificara tarea alguna. La Figura 3.14 muestra distintas imágenes de la base de datos. Las fijaciones se han dibujado sobre las imágenes. Basándose en estos puntos de fijación, se ha generado un mapa de densidad de fijaciones para cada imagen (Bruce y Tsotsos, 2009). Se muestran también en la Figura 3.14, bajo cada imagen original. Figura 3-14: (arriba) Imágenes de la base de datos Toronto anotadas con los puntos de fijación (ver texto); (centro) mapas de densidad de fijaciones obtenidos desde los puntos de fijación de veinte personas; y (abajo) mapas de densidad de fijación obtenidos por el esquema de segmentador y mecanismo de atención propuestos. 68
En la Figura 3.14 se muestran, en la fila inferior, los mapas de densidad de fijación obtenidos usando el sistema propuesto. Para obtener estos mapas se ha fovealizado con un esquema multirresolución de cinco anillos (réxeles de 32, 16, 8, 4 y 2 píxeles de lado) y una fóvea de 176 x 140 píxeles. Las imágenes se han redimensionado a 672 x 512 píxeles, para hacer ambas dimensiones divisibles por 32. El umbral de parecido en color se ha fijado experimentalmente para obtener buenos resultados, pero se ha dejado luego fijo para todas las imágenes de la base de datos. El efecto de suavizado que presentan los mapas de densidad se ha conseguido filtrando, con una Gaussiana, los mapas de saliencia. En este apartado se proporciona una simple evaluación cualitativa del mecanismo de atención, que será completada con datos cuantitativos en el Capítulo 5 de esta Tesis. Frente a la mayoría de los métodos de atención visual, nuestros mapas de saliencia sí que pueden ser estimados desde un conjunto de fijaciones. Sin embargo, en lugar de obtenerse desde un conjunto de puntos de fijación, como se hace con los seguidores de la mirada aplicados a personas, nuestras fijaciones se asocian a regiones y no a puntos bidimensionales de la imagen. Así, los mapas de densidad de fijaciones que se muestran en la fila inferior de la Figura 3.14 se han construido a partir del suavizado de la suma de las n regiones más salientes. El número n es igual a la media de las fijaciones humanas almacenadas para esta imagen en la base de datos original. En la Figura 3.15 se muestran datos parciales que permiten determinar como se obtiene uno de estos mapas de densidad. 3.3. Discusión Los modelos de atención que se presentan en la literatura suelen centrarse en aspectos normalmente relacionados con la identificación de las características que deben influir en la propia atención, con la combinación de estas características para determinar el mapa final de saliencia, o con cómo una tarea específica puede guiar las fijaciones. Pero en general suelen despreocuparse de la naturaleza foveal del sistema de atención humano, en el que dicen normalmente fundamentarse. Los pocos métodos que siguen una estrategia multirresolución suelen emplear para ello dos imágenes, capturadas desde distintas cámaras (Meger et al., 2008): una de baja resolución permite calcular el mapa de saliencia asociado a la escena y otra de alta resolución permite capturar con detalle la región de mayor relevancia. El empleo de una fóvea que sólo captura ciertas regiones de la imagen ha sido propuesto como un método eficiente para comprimir el contenido de la imagen (Geisler y Perry, 1998; Guo y Zhang, 2010). Construido sobre la propuesta de codificación 69
en el siguiente párrafo, el cálculo de los vecinos de cada nodo de BaseRAW (GenerarParametrosBase), tanto la lista acotada que se usará en el BD3P como la lista total (ListaVecinos) -sólo para la baseque será empleada por el bloque Determinar ROI para el cálculos de los contrastes color e intensidad. En el nivel superior de esta pirámide se tendrá un grafo cuyos nodos serán las raíces de las clases en la imagen. Su propagación, por los enlaces entre-nivel, hasta la base permitirá definir la segmentación de la imagen (BaseSEG). Este grafo será la entrada del tercero de los bloques, que lo empleará para estimar las características de evidencia de cada región y estimar el mapa de saliencia, MapaSaliencia. La región más relevante será automáticamente seleccionada como el foco de atención y se estimarán los parámetros {T, B, L, R} de la nueva fovealización. Una segunda opción de trabajo es reducir el lazo a los bloques Video foveal HSV – Segmentador BD3P. El sistema capturará y segmentará imágenes con dimensiones y retinotopología fijas. Todo este esquema ha sido implementado en Lenguaje C y evaluado en un procesador Intel® Core™ 2 Duo T8100 @ 2.10GHz proporcionando resultados correctos, pero con un tiempo de trabajo superior al segundo. Dejando fuera de su ámbito la referida actualización de las listas de vecinos, el primero de los bloques permite ser sintetizado en hardware en toda su totalidad. Por otra parte, la secuencialidad de las acciones que lleva a cabo con los datos el segundo de los bloques, Segmentador BD3P, permitiría organizar su trabajo usando los dos cores del procesador ARM del XC7Z020-CLG484-1. Básicamente la idea sería replicar el software en ambos cores pero procesar con ellos distintos fotogramas, simultaneando en el proceso el trabajo de los dos cores software, el core lógico de captura, y la entrada y salida de datos por los cores AXI Video Direct Memory Access (AXI VDMA). Este aspecto se verá con detalle en el apartado 4.3. 4.2. Implementación del bloque de adquisición de vídeo Cuando hay que pasar de los modelos teóricos a su plasmación en plataformas reales nos encontramos con restricciones que están muy estrechamente relacionadas con el estado de la tecnología disponible en cada momento. En unos casos la tecnología nos condiciona qué es lo que podemos hacer y en cierta manera nos define la metodología de trabajo, basada en las herramientas de desarrollo disponibles. Así las contribuciones relacionadas con este trabajo, siempre han propuesto procesado de imágenes en escala de 76
grises y con dimensiones relativamente reducidas porque era la información que nos suministraba los sensores CMOS disponibles. En la parte de captura y preprocesado de la imagen, la capacidad de integración de los dispositivos programables nos limitaba el número de etapas que podemos integrar en el mismo dispositivo, obligándonos a una integración a nivel de sistema basado en varios circuitos, añadiendo la necesidad de diseño y desarrollo de interfaces a medida. Varios de los desarrollos recopilados en dichas contribuciones se realizan en entornos basados en captura de esquemas y síntesis lógica a partir de descripciones RTL, pues las herramientas de síntesis de alto nivel no están aún muy extendidas, ni disponibles a costes razonables. En cuanto a las alternativas de implementación disponibles, todavía se podía considerar el diseño y fabricación de un ASIC como una opción económicamente viable, dando pie a una línea de trabajo que incluye el diseño de un chip a medida para tareas de segmentación así como una metodología para la creación de vectores de prueba de chip fabrcado, de manera optimizada. Figura 4-2: Diagrama de bloques de la integración del generador de niveles multiresolución, con los circuitos externos de procesado. La Figura 4-2 muestra la integración a nivel del sistema del generador de niveles multirresolución presentado en (González, 2002) con el resto de la cadena de procesado, diseñada e implementada en un ASIC fruto del trabajo de (Coslado, 2004). En este diagrama hay que resaltar la necesidad de definir un interfaz a medida entre ambos subsistemas, basado en una arquitectura de 77 rx(7:0) ad(15:0) bnksel cs2 pix(7:0) pck ldv fdv MCLK dpram port a port b multiresolution levels generator node linking for segmentation CMOS sensor FPGA ASIC control FPGA cs1 dpram port a port b
doble buffer utilizando memorias de doble puerto, con objeto de simplificar el acceso a ese espacio de memoria común. Este acceso hace necesario la integración, junto con el circuito generador de niveles multirresolución, de una etapa de codificación de prioridad, para realizar de forma adecuada la escritura de los diferentes niveles en dichas memorias, como se puede ver en la Figura 4-3. Figura 4-3: Diagrama de bloques del generador de niveles multiresolución que incluye el generador propiamente dicho y el interfaz de acceso a las memorias externas. La evolución de la tecnología nos ofrece hoy en día muchas ventajas en varios de los aspectos estrechamente relacionados con el presente trabajo. En el caso de los sensores de imagen, disponemos a costes muy razonables de sensores CMOS, de calidad equiparable a los CCD, que nos ofrecen altas resoluciones en color, lo que nos permite seguir una línea novedosa con respecto a las contribuciones iniciales. Los dispositivos configurables ofrecen capacidades de integración que nos abren la posibilidad de integrar toda la cadena de procesado en un sólo dispositivo. Entre estos dispositivos configurables disponemos de auténticos SoC, referidos durante todo este documento como AP SoC, que integran en el mismo dispositivo tanto la capacidad de implementar procesadores hardware a medida como la de 78 a+b /2 FIFO FIFO PIX(7:0) RX1 RX2 RX6 a+b /2 FIFO a+b /2 a+b /2 a+b /2 a+b /2 M71 M71 FIFO 1 FIFO 2 a+b /2 FIFO 6 a+b /2 a+b /2 a+b /2 a+b /2 PYRAMIDER RX(7:0) ADDR(15:0) add gen 0 add gen 1 add gen 2 add gen 3 add gen 4 add gen 5 add gen 6 reg 0 reg 1 reg 2 reg 3 reg 4 reg 5 reg 6 sequential priority encoder CS1 OUTPUT STAGETIMING CONTROL REGS AND LEVELS Load Push Pop UL2 reg BR2 reg cmp UL0 reg BR0 reg cmp UL3 reg BR3 reg cmp UL1 reg BR1 reg cmp L0 L1 L2 L3 RX5 RX4 RX3 PIX RW RX1 RX2 RX6 Rdy STR CMD(3:0) DAT(9:0) MCLK PCK LDV FDV RST row count col count CS2 valid rows count valid cols count decoder BnkSel
ejecutar aplicaciones software sobre una unidad de procesado, todo ello integrado gracias a una arquitectura de bus perfectamente definida (ver Figura 4-4), lo que nos libera de la tarea de definir nuevos interfaces de conexión entre la parte hardware y software. Figura 4-4: Arquitectura simplificada de un AP SoC difereciando la parte de procesado software (PS) y la de desarrollo de hardware a medida (PL), unidas mediantes un bus optimizado. Esta plataforma hardware está acompañada de un entorno de desarrollo en el que, entre otras herramientas, disponemos de una de Síntesis de Alto Nivel (de aquí en adelante referida como HLS) que nos permitirá describir nuestros algoritmos en lenguaje C/C++, acelerando el proceso de diseño y verificación de los mismos. La transferencia de datos de video se integra en al arquitectura de bus gracias al estándar AXI4-Stream. El desarrollo de nuestros módulos teniendo en cuenta este marco, simplificará su integración a nivel de sistema. En este apartado se describe el detalle del diseño de cada uno de las etapas que componen la cadena de preprocesado, tal y como se ilustra en la Figura 45, hasta entregar la información a la etapa de procesado cuyo detalle se desarrolla en el Apartado 4.3. Toda la cadena de captura de imágenes del sensor así como su prepocesado, son implementadas en la parte Programmable Logic (de aquí en adelante la parte PL), que en la Figura 4-4 se corresponde con toda la zona amarilla, donde se encuentran los recursos para nuestro hardware a medida 79
Figura 4-5: Cadena de preprocesado desde el sensor hasta la etapa de procesado. Antes de abordar el diseño propiamente dicho, se revisan los aspectos importantes en relación con las estructuras de datos necesarias para los algoritmos de procesado de imagen y de video y los recursos de memoria disponibles para implementar dichas estructuras en la lógica configurable. Estos conocimientos nos permitirán orientar todo el diseño a un resultado óptimo en cuanto a prestaciones y utilización de recursos. Todo el desarrollo se realiza en C/C++ para ser sintetizado con HLS, por lo que es importante revisar las directivas necesarias para controlar el proceso de síntesis, en relación con el uso de los recursos de memoria. 4.2.1. Procesado de imagen y procesado de video La forma en que están disponibles los datos que debemos procesar, tanto espacial como temporalmente, condiciona fuertemente el diseño de nuestro algoritmo así como de las estructuras de datos sobre las que vamos a trabajar. Figura 4-6: Distribución de los datos a procesar en una imagen estática y en una secuencia de video. Las celdas grises indican datos listos para ser procesados. Nuestros algoritmos de procesado software pueden trabajar sobre los datos que componen una imagen estática, que están organizados como un array bidimensional y al que podemos acceder controlando los índices y el rango de 80 AXI4 stream bayer2rgb Ov5642 (5Mpx) Rexelizador RGB/Y RGB2HSV AXI4 stream AXI4 stream Vid 2 AXI stream vid Sensor I/F vid AXI4 stream procesado preprocesado 123 14 15 6 16 7 25 26 27 28 29 30 31 32 17 18 19 910 20 11 12 21 22 23 24 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 22 63 64 84 5 13 1 2 3 14 15 6 16 7 25 26 27 28 29 30 31 32 17 18 19 910 20 11 12 21 22 23 24 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 22 63 64 84 5 13
los mismos, para trabajar con cualquier zona de dicha imagen. Los datos están siempre disponibles, lo que nos permite en cualquier momento seleccionar la zona de trabajo o ventana de procesado, con las dimensiones que se necesiten (en la Figura 4-6 de la izquierda, zonas de 2x2 ó 4x4), y en el orden que se desee, pudiendo empezar por la parte superior de la imagen, bien por la izquierda bien por la derecha, o empezar por la parte inferior de la misma. Cuando la imagen a procesar proviene directamente de un sensor que nos entrega los datos de forma progresiva, las ventanas de procesado van a estar disponibles con todos sus datos, en un orden y en un instante muy definido. En la Figura 4-6 de la derecha, podemos ver que las ventanas de procesado y la generación de los resultados asociados a ellas, van a estar disponibles progresivamente, desde arriba hacia abajo y de izquierda a derecha. La primera ventana destacada, pudo ser procesada cuando se dispuso de los datos número 9 y 10, que pertenecen ya a la segunda fila. La segunda ventana resaltada, no podrá ser procesada hasta que no se disponga del dato número 14. Para procesar la última ventana resaltada, habrá que esperar a tener datos que pertenecen al final de la imagen. Los sensores de imagen entregan la información en un flujo o streaming de datos continuo, por lo que, una vez entregado, un dato no vuelve a estar disponible. Si tenemos en cuenta que los datos que completan una determinada ventana de procesado pertenecen a distintas filas, se hace necesario el diseño e implementación de estructuras de memoria locales que nos permitan almacenar toda esa información que ha sido recibida, a la espera de la llegada de los datos que nos interesan. Así, volviendo al ejemplo que nos muestra la Figura 4-6 de la derecha, debemos almacenar los datos del 3 al 8 pertenecientes a la primera fila, para poder completar la ventana con los datos 9 y 10 que pertenecen a la segunda fila. Podemos concluir que los bufferes de memoria son una pieza clave para los algoritmos de procesado de video. Estas estructuras nos permiten mantener los contextos espacial y temporal necesarios para que una aplicación pueda trabajar sobre el dato actual. Cuando nuestro objeto es implementar este procesamiento en una determinada plataforma hardware, estas estructuras tienen impacto en la latencia, rendimiento, complejidad del procesamiento, y sin olvidar el correcto funcionamiento. 4.2.2. Recursos de memoria en la FPGA Los bufferes de memoria que en el apartado anterior se han presentado como pieza clave en la implementación de algoritmos de procesado de video en 81
particular, necesitan de la disponibilidad de unos recursos en la tecnología que vamos utilizar. Las diferentes generaciones de FPGA que han ido apareciendo en el mercado, han ofrecido esta capacidad de implementar bloques de memoria empotrada dentro del propio dispositivo. Las características de estos recursos definen la arquitectura de memoria de dicha FPGA. Conocer las posibilidades que ofrece esta arquitectura es importante para orientar nuestro modelo RTL o de alto nivel, con el fin de que la síntesis e implementación, ya no sólo sea óptima, sino simplemente posible. Por otra parte, la cantidad de recursos disponibles nos definen el tipo de estructura de memoria que podemos diseñar en nuestro sistema. Esta capacidad de memoria depende mucho del tipo de recurso utilizado, dentro de los que disponemos en la tecnología seleccionada. La Tabla 4-1 recoge de forma resumida, la evolución de estos recursos en función de la familia de dispositivo, así como los tipos de memoria de los que disponemos dentro de estas arquitecturas. Un dato muy importante recopilado en esta tabla, es la máxima cantidad de memoria que podemos implementar dentro de la propia FPGA en función del tipo de recurso utilizado, que en cualquiera de los casos, están en unos órdenes de magnitud muy por debajo de las capacidades de almacenamiento que nos ofrecen los circuitos externos de memoria. FF Max RAM (LUT) Max BRAM (18Kb) BRAM (36Kb) Max min max (Kb) min max (Kb) min max min max (Kb) Spartan-6 4800 184304 180 1200 5420 1355 12 268 - - 4824 Artix-7 20800 269200 262 800 11550 2888 312 1440 156 720 25920 Virtex-4 12288 178176 174 6144 89088 1392 48 336 - - 6048 Virtex-5 19200 207360 202 4800 51840 3520 64 576 32 288 10368 Virtex-6 93120 948480 926 4180 33120 8280 312 1440 156 720 25920 Virtex-7 728400 2443200 2385 27750 86200 21550 1590 5168 795 2584 93024 Zynq 35200 554800 541 5280 83220 5200 120 1530 60 755 27180 Tabla 4-1: Recursos de memoria disponibles en las últimas familias de FPGA de XILINX 4.2.2.1. Flip Flops Es el elemento más básico para construir estructuras de memoria. Los ocho Flip-Flop disponibles en un mismo SLICE permiten implementar un registro de 8bit, y con varios SLICE podemos configurar el banco de registros con las 82
dimensiones necesarias en nuestro procesamiento. Ofrecen la máxima versatilidad y ancho de banda tanto en escritura como en lectura, pero cuando las dimensiones de estas memorias son de valores medio-alto, suponen un uso muy ineficiente de los recursos de la FPGA. 4.2.2.2. Memoria Distribuida Los generadores de función (LUT) disponibles en los SLICEM pueden ser configurados como pequeños bloques de memoria de escritura síncrona y lectura asíncrona. Combinando las cuatro LUT disponibles dentro del mismo SLICEM, se pueden crear bloques con diferentes e interesantes configuraciones como se puede observar en la Tabla 4-2, de entre las que destaca las configuraciones multipuerto. Estas configuraciones multipuerto permiten aumentar el ancho de banda de las lecturas, a costa de un incremento notable en la cantidad de recursos utilizados: lo podemos ver en la tabla como, por ejemplo, una memoria de 64 palabras de cuádruple puerto requiere cuatro veces más recursos que una de simple puerto y la misma capacidad. RAM Descripción Número de LUT 64 x 1S Single port 1 puerto escritura/lectura 1 128 x 1S 2 256 x 1S 4 64 x 1D Dual port 1 puerto escritura/lectura; 1 puerto de lectura 2 128 x 1D 4 64 x 3SDP Simple dual port 1 puerto escritura; 1 puerto de lectura 4 32 x 6SDP 4 64 x 1Q Quad port 1 puerto escritura/lectura; 3 puerto de lectura 4 32 x 2Q 4 Tabla 4-2: Diferentes configuraciones de memoria mediante la combinación de las 4 LUT disponibles dentro de un mismo SLICEM 4.2.2.3. Memoria Dedicada Cuando se necesitan memorias de mayor tamaño del que reflejan los datos de la Tabla 4-2, sería necesario combinar los recursos de un SLICEM con los de otros SLICEM, y esto se implementa de forma ineficiente. Así, cuando los requisitos de memoria son más importantes, es necesario emplear los bloques de memoria dedicada denominados BRAM (ver Figura 4-7). A diferencia de la 83
RAM distribuida, la capacidad es mucho mayor y tanto la escritura como la lectura son síncronas. Figura 4-7: Bloque de memoria de 36Kb con 2 puertos de escritura/lectura y array de memoria compartida. Puede ser configurado como dos bloques de memoria de doble puerto de 18Kb cada uno, totalmente independientes. Aunque el número de puertos disponible se limita a un máximo de dos, la anchura de datos de cada uno de ellos si es configurable de manera muy interesante tal y como se resume en laTabla 3. Estas posibles configuraciones permiten adaptar los bloques de RAM utilizados a la anchura de datos de nuestras unidades de procesamiento, es por lo tanto muy deseable ajustar ambos parámetros para un óptimo aprovechamiento de los recursos disponibles. Modo de configuración BRAM 18Kbit BRAM 36Kbit Descripción Single Port 16Kx1, 8Kx2, 4Kx4, 2Kx9, 1Kx18 32k x 1, 16Kx2, 8Kx4, 4Kx9, 2Kx18, 1Kx36 1 puerto de escritura/lectura Lectura O escritura en 1 ciclo True Dual Port 16Kx1, 8Kx2, 4Kx4, 2Kx9, 1Kx18 32Kx1, 16Kx2, 8Kx4, 4Kx9, 2Kx18, 1Kx36 Dos puertos de escritura/lectura totalmente independientes Dos operaciones en 1 ciclo Simple Dual Port 16Kx1, 8Kx2, 4Kx4, 2Kx9, 1Kx18, 512x36 32K x 1, 16Kx2, 8Kx4, 4Kx9, 2Kx18, 1Kx36, 512x72 1 puerto de lectura y 1 puerto de escritura Lectura y escritura en 1 ciclo Tabla 4-3: Posibles configuraciones de los bloques BRAM tanto en modos de funcionamiento como en la anchura de los buses de datos. Podemos concluir de esta breve revisión de los recursos de memoria que el mayor ancho de banda se obtiene con estructuras basadas en Flip-Flop; que estructuras de datos importantes necesitan del uso de los BRAM; y que la 84
memoria distribuida es una solución eficiente y flexible cuando la cantidad de memoria requerida encaja dentro de los recursos disponibles en un mismo SLICEM. 4.2.2.4. Síntesis de Memoria Los recursos para implementar estructuras de memoria son limitados y debe cuidarse su generación a partir de la síntesis, ya sea síntesis lógica o síntesis de alto nivel. En ambos tipos de síntesis, para crear estructuras de memoria hay que declarar arrays. En el caso de la síntesis lógica, la forma de actualizar y leer sus contenidos determina qué tipo de recurso, de los revisados anteriormente, se generará: si los contenidos son inicializables se crearán registros basados en Flip-Flop; si los contenidos no son inicializables y son leídos de manera asíncrona se crearán registros basados en LUT; y si los contenidos no son inicializables y son leídos de manera síncrona se utilizarán bloques de memoria dedicada o BRAM. Cuando trabajamos con síntesis de alto nivel (HLS), no hay referencia explícita en el modelo a la señal de reloj, por lo que no se puede diferenciar entre accesos de tipo síncrono o asíncrono. HLS por defecto transforma los arrays utilizados en el modelo en BRAM. A menudo este funcionamiento es útil debido a que los bancos de registros son muy costosos, en términos Flip-Flop o LUT necesarios. No obstante las FPGA tienen un número bastante limitado de BRAM, como hemos podido ver en la Tabla 4-1. Por otro lado, los BRAM solo tienen dos puertos de acceso, lo que significa que, como máximo, solo se pueden realizar dos accesos simultáneos a la RAM, y esto puede limitar de manera seria el potencial paralelismo de nuestro diseño. A diferencia de la síntesis lógica, la manera de controlar la generación de un tipo u otro de recursos de memoria está en el empleo de directivas de síntesis, que no forman parte el propio modelo desarrollado. La Tabla 4-4 recoge algunas de estas directivas relacionadas con los bloques de memoria. Por ejemplo, si HLS utiliza un BRAM donde no nos interesa, aplicamos la directiva ARRAY_PARTITION con el tipo definido como COMPLETO y la dimensión fijada a 1, y forzaremos a que el array se implemente como registros, lo que supone un consumo importante de recursos pero nos ofrece un mayor paralelismo. Si deseamos ahorrar en numero de bloques BRAM utilizados, la directiva ARRAY_MAP nos permite unir múltiples arrays más pequeños en uno más grande, que pueda ser implementado en menos BRAM. 85
Figura 4-9: Diagrama de bloques de un sensor CMOS En el diagrama debemos destacar que la información de cada pixel, a la salida del convertidor analógico/digital es de 10bit, resolución que se pierde en la etapa de compresión y formato, donde se generan y ofrecen los formatos habituales en la visualización de vídeo, tal y como aparecen recopilados en la Tabla 4-5 anterior. Esta opción es la más simple de manejar y la recomendada por el fabricante del sensor, pero si queremos trabajar con la máxima resolución tenemos la opción de trabajar directamente en el formato RAW RGB de 10bit, y realizar nuestro propio “revelado digital” de la imagen captada por el array del sensor, para reconstruir por interpolación la información completa de todos los componentes del color para cada pixel, ofreciendo al resto de la cadena de procesamiento un formato RGB888 (24 bit por pixel) o incluso un RGB101010 (30 bit por pixel) si fuera necesario. Esta opción también nos permitirá modificar y probar diferentes mecanismos de interpolación, y no estar sujetos al que implementa el propio sensor en su etapa de procesamiento digital de la señal (DSP), que por lo general suele ser el más simple en el que el valor de los colores que faltan en cada píxel toma el del píxel vecino del mismo color. 4.2.4.1. Temporización de las salidas de un sensor A la hora de poder procesar la información que genera un sensor de video, tan importante son los propios datos que componen cada una de las imágenes, 92
como la señales de temporización que las acompañan. Como podemos ver en la Figura 4-10, la región activa es la zona donde se encuentran los píxeles que componen la imagen, y es la zona donde nuestro algoritmo debe trabajar. Las regiones de blanking, tanto horizontal como vertical, proporcionan el intervalo necesario para que los equipos de video detecten y visualicen correctamente estos contenidos. Figura 4-10: Formato básico de un frame de video que diferencia la región activa de las zonas de blanking, junto con las señales de sincronismo asociadas. No todas las señales mostradas en la figura necesariamente han de ser generadas por el sensor. Así por ejemplo, podemos ver en el diagrama de bloques del sensor, que las señales de temporización generadas por el bloque correspondiente son solamente las del pulso de sincronización vertical (VSYNC) que indica la finalización de un frame y por lo tanto, el inicio de uno nuevo, y la señal HREF que no es otra que la señal complementaria de la de Blanking Horizontal (H Blank). El aspecto que ofrecen las señales de sincronismo que entregan los sensores de imagen, se resumen en la Figura 4-11. 93
Figura 4-11: Señales de sincronismo asociadas al flujo de datos generado por un sensor de video. En la parte superior de la Figura 4-11 se ilustra el sincronismo vertical, definido por la señal VSYNC, cuya frecuencia define los frames por segundo que está entregando el sensor. Cada frame está compuesto por tantas líneas como pulsos de la señal HREF hay entre dos pulsos consecutivos de de VSYNC. En la parte inferior se ilustra la temporización de línea, en la que podemos observar que solo se generan datos válidos mientras la señal HREF está activa. El resto de tiempo, que es el intervalo de blanking, no hay datos válidos, representado por un valor constante en el bus de datos (valor 0x10 en el ejemplo). Todas las señales están sincronizadas con la señal de reloj denominada PCLK, y los datos válidos se suceden al ritmo de un nuevo dato cada ciclo de PCLK. La frecuencia de PCLK fija el bitrate del flujo de datos y define un parámetro fundamental a la hora de modelar e implementar las distintas unidades de procesamiento que han de tratar los datos generados por el sensor. Esta frecuencia depende de la resolución y el el frame rate seleccionado en el sensor, como se puede ver en la Tabla 4-6: Resolución Frame Rate Frecuencia PCLK 2592x1944 15 fps 80 MHz 1920x1080 30 fps 70 MHz 1280x720 60 fps 60 MHz 640x480 60 fps 20 MHz 320x240 120 fps 10 MHz Tabla 4-6: Frecuencias de la señal de reloj de pixel (PCLK) en función de la resolución y el frame rate Las señales de sincronización son fundamentales para dar formato apropiado al flujo de datos de video. Aunque no son el objeto principal de nuestros 94 VSYNC HREF p0 p1 pN-3 pN-2 pN-1x10 p0 p1x10x10pN-6 pN-5 pN-4p2 p3 p4 p5 HREF PCLK DATA
algoritmos, estas señales deben ser adecuadamente interpretadas para que los resultados generados puedan ser procesados por otros bloques o equipos. Si bien este esquema de temporización mostrado es el más habitual a la salida de nuestros sensores o a la entrada de los equipos de visualización, no es el único ni el más interesante a la hora de modelar nuestros algoritmos de procesamiento de video, que van a ser integrados junto con otros bloques dentro de un mismo sistema integrado en un solo chip. El esquema de temporización mostrado en la Figura 4-12, se centra en los propios datos que conforman la imagen a procesar, identificando claramente el primer dato o píxel de la imagen (con la generación del pulso SOF) así como el último píxel de cada una de las líneas de dicha imagen (con la generación del pulso EOL). Figura 4-12: Esquema de temporización de un flujo de datos basado en la identificación del primer pixel de la imagen y del último pixel de cada línea. Cuando trabajamos con HLS, debemos definir de manera explícita en nuestro modelo C/C++ cómo vamos a procesar las señales de sincronización del esquema de la Figura 4-11, puesto que esta herramienta es de propósito general y no tiene ningún conocimiento específico sobre procesado de video y en particular desconoce el significado de dichas señales de sincronismo. Esto hace que el modelo de nuestros algoritmos deba contemplar esta dificultad añadida, lo que dificulta el mantenimiento y modificación de nuestros algoritmos, además de que no nos sirva el esquema tradicional en procesado de video en términos de bucles sobre filas y columnas cuando utilizamos C/C+ + para el modelado. Xilinx suministra una solución a nivel de sistema que nos permite obviar el procesamiento de la señales de sincronización a la hora de hacer la captura de nuestro diseño para ser implementado mediante HLS. Esta solución es posible gracias a la utilización de dos IP cores: “Video In to AXI4-Stream” (PG043, 2014) que nos permiten transformar el flujo de datos según el esquema de la 95
Figura 4-11 en un flujo de datos según el esquema de la Figura 4-12; y “AXI4Stream to Video Out” (PG044, 2014) que nos permite hacer la transformación en sentido contrario. Utilizando estos cores en nuestra cadena de procesamiento, podemos capturar nuestros algoritmos en términos de filas y columnas, tal y como se ilustra en el siguiente código: Listado 5: Plantilla para la captura de algoritmos de procesado voidvideo_proc(input_pixels,output_pixels,height,width){ for(row=0;row<height;row++){ for(col=0;col<width;col++){ //algoritmoparaelprocesadodelospixeles } } } El código del Listado 5 muestra la plantilla recomendada y seguida en el presentre trabajo para modelar algoritmos de preprocesado de video con la herramienta HLS. A nivel de implementación hardware, la propuesta basada en estos cores y el uso de este esquema de codificación, resulta en el diagrama de bloques que se muestra en la Figura 4-13. Figura 4-13: Diagrama de bloques de la cadena de procesamiento de video en Vivado HLS En esta cadena de procesamiento, los dos IP cores aparecen al principio y al final de dicha cadena, y en la parte central se suceden las etapas de procesado creadas con la herramienta HLS y siguiendo la plantilla del Listado 5. Esta estructura y metodología es la que se ha seguido para crear y conectar las diferentes etapas de captura y preprocesado de la imagen suministrada por el sensor. 96
4.2.5. Interpolación de los valores del color Tanto los sensores CCD como los sensores CMOS generan la información de color de sus píxeles haciendo uso de un filtro de color en forma de array, conocido como CFA o CFM (Color Filter Array o Color Filter Mosaic) de manera que cada píxel sólo tiene información de un color. Para obtener la información de los demás colores para cada píxel, es necesario un proceso de reconstrucción normalmente conocido como interpolación o demosaicing. Este proceso, en muchos casos, es una opción disponible dentro del mismo sensor, en una de sus etapas de procesado, pero también es cierto que hay sensores que no la integran y sólo tienen la opción de entregar los valores no reconstruidos para cada píxel: es lo que se conoce como formato RAW. Figura 4-14: Distribución tipo Bayer de los filtros de color RGB sobre la matriz de un sensor de imagen Aunque no es el único CFA utilizado, la mayoría de los sensores en la actualidad hacen uso del patrón Bayer (B.Bayer, 1976), cuyo aspecto es el de la Figura 4-14. En los últimos años han aparecido propuestas alternativas al clásico patrón Bayer, buscando mayor calidad en situaciones de captura de imagen exigentes. Concretamente el objetivo de estos últimos es ofrecer mayor brillo en capturas de alto contraste y un menor ruido en capturas en condiciones de baja luminosidad. Como se puede observar en la Tabla 4-7, en la matriz de filtros de color, algunas de las posiciones ocupadas por el filtro verde han sido reemplazadas por filtros transparentes, buscando una mayor captación de luz (Aptina, 2013). 97
Tabla 4-7: Resumen de los nuevos CFA (Color Filter Array) propuestos comparados con el patrón Bayer como referencia. A pesar de ciertas mejoras obtenidas por las nuevas propuestas, el patrón de Bayer sigue siendo el más empleado, y los métodos de interpolación basados en este patrón también han sido los más estudiados, desde métodos de interpolación lineal computacionalmente más simples (Sakamoto,1998) hasta propuestas mejoradas que requieren más capacidad de procesamiento (Ramanath, 2002; Malvar, 2004) . 4.2.5.1. Modelado e implementación del filtro de interpolación Como ya hemos comentado anteriormente, los sensores comerciales ofrecen como método de interpolación el más simple de los conocidos, el del vecino más próximo, en el que cada pixel de salida interpolado se le asigna el valor del píxel más próximo en la imagen de entrada. Si hay varios vecinos con la misma distancia, se elige uno de ellos. Además, estos sensores no ofrecen a la salida el resultado completo de la interpolación, sino que muestran a la salida ese resultado comprimido en algunos de los formatos estándar que hemos revisado. Estas dos razones motivan el hecho de que se decida incluir como primer bloque de preprocesado, el filtro de interpolación que nos permitirá, como características principales, disponer de la máxima información de color para cada píxel, evitando así la etapa de compresión de datos, y la posibilidad de implementar y probar con diferentes métodos de interpolación. 98
Figura 4-15: Patrón de Bayer para la captura de color junto con los filtros de interpolación bilineal comúnmente utilizados (Sakamoto, 1998) . En la Figura 4-15a reproducimos el patrón de Bayer para facilitar la interpretación del método básico implementado en esta propuesta. Como se sugiere en (Sakamoto,1998), los valores de los componentes que faltan en cada pixel de entrada, son interpolados linealmente a partir de los valores de los píxeles vecinos del mismo color, teniendo en cuenta que la ventana de interpolación es una matriz de 3x3 centrada en el píxel que estamos procesando. Para el cálculo de los componentes R y B, nos encontramos con cuatro posibles casos, ilustrados en la Figura 4-15b,c,d y e. Si R y B se calculan para un píxel tipo G, el promediado se hace con los dos píxeles más próximos del mismo color. Cuando el componente B se calcula para un pixel tipo R (Figura 415d), o bien el componente R se calcula para un píxel tipo B (Figura 4-15e) el promediado se realiza con los cuatro píxeles vecinos del tipo B y R respectivamente. Para el cálculo del componente G, nos encontramos con dos posibles situaciones, ilustradas en la Figura 4-15d y e. En ambos casos el cálculo requiere el promediado de los 4 vecinos del tipo B. El modelado de estos cálculos, para la posterior síntesis e implementación de los mismos, se ha realizado en base a la definición de distintos kernel de filtrado de tamaño 3x3, que se aplican de forma secuencial recorriendo la totalidad de la imagen a medida que es entregada por el sensor. De la explicación en los párrafos previos, se pueden determinar los cuatro kernel distintos que son necesarios y que se recogen en la Figura 4-16. 99 Gr RGr R R R Gb GbB B Gb GbB B R R B B R R B B R B B B B R R R R B (b)(a) (c) (d) (e) Gr R R GbB GbB R R Gb GbB B R GbB Gr Gr Gr Gr Gr Gr Gb Gb Gb Gb Gr Gr Gr Gr Gb Gb Gr Gr Gr Gr Gb Gr Gr Gb Gb
Figura 4-16: Matrices de interpolación para los distintos casos identificados: a) calculo de G en un pixel R ó B; b) cálculo de R en un pixel B, o cálculo de B en un pixel R; c) cáculo de B en un pixel Gr, o cácuo de R en un pixel Gb; d) cálculo de B en un píxel Gb o cálculo de R en un pixel Gr. Estos kernel son aplicados de forma concurrente a los datos de entrada que se están procesando, de manera que los valores correctos para cada pixel procesado se seleccionan en función de la posición de dicho pixel en el patrón de Bayer. Como se observa, los kernel no incluyen el factor de división requerido en cada promediado (4 en los casos a y b; 2 en los casos c y d), con el objeto de poder trabajar con aritmética entera sin acumular el error por redondeo. El promediado se realiza en la última etapa del cálculo. Siguiendo una vez más lo sugerido en (Sakamoto,1998), los resultados de la interpolación del color G, pueden mejorarse si se implementa una interpolación adaptativa que tenga en cuenta la correlación de valores de los píxeles vecinos. Como podemos observar en la Figura 4-17, la ventana de procesado pasa ahora a tener una dimensión de 5x5, y nos muestra los dos posibles casos que se nos puede presentar. Figura 4-17: Ventanas de procesamiento para el cálculo del componente G mediante interpolación adaptativa. En la Figura 4-17a, el valor del componente G debe ser calculado para un píxel de entrada de tipo R. Este valor viene dado por el siguiente promediado: 100 0 1 1 0 1 0 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 101 0 000 (a) (b) (c) (d) R R3 G3 R1 G1 G2G4R4 R2 G3 G1 G2G4 B B3 B1 B4 B2 (a) (b)
G(R) = (G1 + G3) / 2, si | R1– R3 | < | R2 – R4 | (G2 + G4) / 2, si | R1– R3 | > | R2 – R4 | (G1 + G2 + G3 + G4) / 4, si | R1– R3 | = | R2 – R4 | Es decir, se tiene en cuenta la correlación en el componente R para adaptar el método de interpolación. Si la diferencia entre R1 y R3 es menor que la diferencia entre R2 y R4, indicando que la correlación es mayor en sentido vertical, utilizamos la media de los vecinos verticales G1 y G3 para calcular el valor buscado. Si es la correlación horizontal la más fuerte, utilizamos los vecinos horizontales. Si ninguna de los correlaciones es dominante, utilizamos los cuatro vecinos para hacer el promediado. De manera análoga, el componente G para un píxel de entrada del tipo B (Figura 4-17b), se calcula como: G(B) = (G1 + G3) / 2, si | B1– B3 | < | B2 – B4 | (G2 + G4) / 2, si | B1– B3 | > | B2 – B4 | (G1 + G2 + G3 + G4) / 4, si | B1– B3 | = | B2 – B4 | La infraestrutura de este core basado en una ventana de procesado de dimensiones 5x5, puede ser utilizada para implementar otros algoritmos de reconstrucción bilineal que necesiten de este tamaño de ventana de procesado, como es el caso de la propuesta de (Malvar, 2004). 4.2.5.2. Generación del nivel de gris para cada pixel En el apartado anterior se ha revisado con detalle cómo se obtienen los valores de los tres componentes del color para cada uno de los píxeles de la imagen. Podemos aprovechar que tenemos disponibles los valores calculados de estos componentes de color para, a partir de ellos, obtener el valor en escala de grises que corresponde a ese píxel. Siguiendo la recomendación de (ITUR BT.601, 2013), el nivel de gris de un píxel se puede reconstruir aplicando la siguiente fórmula: Y = 0,299R + 0,587G + 0,114B El modelado directo de esta expresión es posible, pero significa la implementación de aritmética en punto flotante. Con objeto de operar con aritmética entera, y el ahorro en recursos lógicos que eso supone, la expresión 101
4.2.7. Conversión entre los espacios RGB y HSV El espacio de color RGB es el más adecuado para mostrar imágenes en dispositivos de visualización, además de ser el utilizado por los sensores cuando entregan las imágenes en modo RAW. Pero a la hora de realizar procesado de imagen y video no es el más indicado, al no tener las componentes de luminancia y crominancia por separado. Uno de los espacios de color ampliamente utilizado en tareas como segmentación, es el espacio HSV. (a) (b) Figura 4-23: El espacio de color HSV puede ser representado por un cilindro y el espacio RGB como un cubo. La conversión entre estos dos espacios de color se trata básicamente de una transformación entre coordenadas cartesianas y coordenadas cilíndricas. Su formulación está ampliamente documentada y es empleada en multitud de trabajos de procesado de imagen donde se pone énfasis en la necesidad de trabajar en el espacio HSV (Deswal, 2014, Chmelar, 2014), así como el interés en su implementación hardware (Hamachi, 2013). La cadena de preprocesado propuesta en este trabajo incluye, en su última etapa, la conversión de los valores RGB a HSV, para su posterior utilización por los algoritmos de segmentación. Una vez realizado el procesado de la imagen, antes de poder realizar su visualización, es necesario incluir una etapa de conversión de los valores HSV a RGB. Esta conversión sólo necesita los valores de un único píxel, por lo que no es necesario estructuras de almacenamiento temporal: ni ventanas de procesado ni bufferes de línea. Por lo tanto, la solución propuesta para su implementación 108
debe atender a la optimización en cuanto a los operadores aritméticos utilizados así como la resolución de dichas operaciones, sin comprometer la funcionalidad. Trabajar con aritmética en punto flotante nos ofrece la precisión necesaria, a costa de unos altos requerimientos de recursos de la FPGA, máxime teniendo en cuenta que la tecnología con la que trabajamos no dispone de unidades de procesamiento en punto flotante. La alternativa es utilizar la aritmética en punto fijo, con unos requerimientos de recursos menos exigentes pero a costa de una menor precisión. 4.2.7.1. Conversión de RGB a HSV A partir de los valores normalizados R'=R/255, G'=G/255 y B'=B/255 podemos calcular los siguientes parámetros: Cmax = max ( R', G', B' ) Cmin = min ( R', G', B' ) ∆ = Cmax - Cmin Con los valores normalizados y los parámetros calculados, las ecuaciones que nos permiten realizar la transformación del espacio RGB al espacio HSV son las siguientes: H = 0 , si ∆ = 0 60 x ( ( G'-B' ) / ∆ mod 6 ) , si Cmax = R' 60 x ( ( B'-R' ) / ∆ + 2 ) , si Cmax = G' 60 x ( ( R'-G' ) / ∆ + 4 ) , si Cmax = B' S = 0 , si Cmax=0 ∆ / Cmax , si Cmax ≠ 0 V = Cmax donde los valores generados cumplen que 0 ≤ H < 360, 0 ≤ S ≤ 1 y 0 ≤ V ≤ 1. Todas las operaciones que se emplean en las ecuaciones anteriores son sintetizables por la herramienta HLS, dependiendo la cantidad de recursos utilizados del tipo de datos que utilicemos. 109
4.2.7.2. Conversión de HSV a RGB A partir de los valores H,S y V, la reconstrucción del valor RGB correspondiente viene definido por las siguientes ecuaciones: Al igual que en la otra conversión, todas las operaciones que se emplean en las ecuaciones anteriores son sintetizables por la herramienta HLS, dependiendo la cantidad de recursos utilizados del tipo de datos que utilicemos. Como ya hemos comentado, la aritmética en punto flotante está soportada por la herramienta de síntesis, ofreciendo resultados con la precisión requerida, siendo las dos conversiones completamente reversibles, permitiendo recuperar el valor en el espacio de color original. Pero cuando nuestro objetivo es la integración en una plataforma empotrada, habrá que tener en cuenta la transferencia de resultados generados a otras etapas de procesado, a través de los buses disponibles. Habrá que sopesar la viabilidad de trabajar con la máxima precisión posible manteniendo la conectividad. 4.3. La conexión entre la parte HW y la parte SW Una vez descritos los detalles del diseño y desarrollo de los bloques que componen el subsistema que se ha implementado en la parte PL del AP SoC, que constituyen la cadena de preprocesado necesario para generar una imagen multiresolución sobre la que trabajará el algoritmo de segmentación, y antes de entrar en la descripción de los detalles del desarrollo softeware de dicho algoritmo, dedicamos este apartado a definir la arquitectura propuesta en esta Tesis para la integración de todo el sistema en el mismo chip. Como ya anticipamos, la clave está en el acceso compartido que, tanto hardware como 110
software, han de hacer a la misma memoria DDR donde se almacenan los sucesivos frames capturados y que ha de ser procesados. 4.3.1. La estructura de bloques del sistema En la Figura 4-24 se muestra donde se encuentran encuadrados todos los bloques desarrollados como hardware a medida para la parte PL. Figura 4-24: Diagrama de bloques de la distribución de los distintos procesos entre la parte PS y la parte PL del APSoC. A la DDR se accede desde el controlador asociado a la parte PS. Las imágenes multiresolución generadas por la cadena de preprocesado se almacenan en DDR a través de los bloques AXI-VDMA y los canales de altas prestaciones AXI-HP. El procesado SW se realiza en la parte PS, y las imágenes resultantes de dicho procesado quedan almacenados en otra zona de la memoria DDR, de donde son recuperadas por otro bloque AXI-DMA a través de otro canal de altas prestaciones AXI-HP para pasarlas al canal de salida, donde se recupera el espacio de color RGB y ser visualizado en un dispositivo externo a través del controlador de display. Como se observa en el diagrama se han utilizado dos ipcores AXI-VDMA independientes, uno para la entrada y otro para la salida de vídeo. Esto se he hecho así porque queremos que trabajen de forma independiente, y no queremos que se sincronicen internamente a través de los modos de “genlock”. Para un canal de vídeo normal sería deseable que el AXI-VDMA sea el mismo y que sus canales de entrada y de salida “se hablen” para que cada uno sepa qué frame está en uso por el otro. 4.3.2. La organización del espacio de memoria En nuestra propuesta de funcionamiento, como queremos procesar el vídeo por software en el ARM de la parte PS, la gestión al acceso a la memoria será 111 PS PL bayer2rgb Rexel RGB rgb2hsv AXIS Vid 2 AXI stream ov5642 I/F vid AXI VDMA preprocesado AXIS AXIS AXIS processing_system AXI VDMA DDR3 hsv2rgb AXIS AXI stream 2 Vid vid AXIS Display ctrl AXI_HP0 AXI_HP1 - segmentación - estimación foco de atención
diferente al de un canal de video normal: como podemos ver en la Figura 4-25 en la memoria DDR tendremos varios frames de vídeo definidos con la idea de que el software le diga al VDMA de entrada dónde debe guardar el video entrante, y al VDMA de salida de dónde leer la imagen que se está representando en el HDMI. Esto nos permite tener el control completo sobre el flujo de la imagen. Figura 4-25: Segmentación del espacio de memoria para el procesado de los distintos frames El funcionamiento, de manera muy esquematizada, sería el siguiente: 1. El canal de entrada de vídeo está volcando la imagen del sensor en el frame 0; 2. El core 0 del ARM está leyendo la imagen del frame 1 y generando el resultado de la imagen segmentada en el frame 3; 3. El core 1 del ARM está leyendo la imagen del frame 2 y generando el resultado de la imagen segmentada en el frame 4; 4. El canal de vídeo de salida está mostrando la imagen que hay en el frame 5 en el monitor por la salida HDMI. Cuando uno de los cores del ARM, por ejemplo el Core 0, haya terminado su tarea de segmentación, se procederá como sigue: 112 FRAME 0 FRAME 1 FRAME 2 FRAME 3 FRAME 4 FRAME 5 MEMORIA DDR SENSOR CANAL ENTRADA VIDEO CORE ARM 0 (procesado software) CANAL SALIDA VIDEO CORE ARM 1 (procesado software) MONITOR HDMI
1. Se le indica al canal de entrada de vídeo que el siguiente frame donde escribir es el frame 1; 2. Se le dice al canal de salida de vídeo que el siguiente frame de donde leer es el frame 3 (acaba de ser generado); 3. Se le dice al core 0 del ARM que ahora le toca leer la imagen del frame 0 y generar el resultado en el frame 5. Con este esquema se consigue procesar de forma más fluida los frames procedentes del canal de video de entrada, y tenerlos disponibles para su visualización a través del canal de video de salida. 4.4. Implementación de los bloques de Segmentación y Estimación de la posición del Foco de Atención Si el proceso de adquisición de la imagen, conversión de color y fovealizado han sido llevados con éxito a la parte lógica del AP SoC XC7Z020-CLG484-1, el algoritmo de segmentación y estimación de la nueva región de interés, los bloques Segmentador BD3P y Determinar ROI de la Figura 4.2, siguen una estrategia secuencial, más adecuada de ubicar en la parte software del AP SoC. El diagrama de secuencias en el que se gestiona la segmentación de la base multirresolución se presenta en la Figura 4-26. Básicamente, el principal consta de un bucle continuo de movimientos de fóvea, en el que se segmenta la imagen, se estima una nueva posición de la fóvea y se captura una nueva imagen. En concreto, la segmentación se inicia con la lectura del nuevo grafo, que almacena la imagen multirresolución como un vector (BaseRAW). Este vector unidimensional almacena el valor HSV de cada nodo del grafo, y el índice o posición en el vector nos indica su posición en la retinotopología (ver Capítulo 3). Sin embargo falta por completar la información referida a sus vecinos en la retinotopología (acotados a un número máximo y a ser similares en color). Esta información se completa usando la función GenerarParametrosBase. Simultáneamente, esta función completa información adicional sobre los nodos, necesaria para el cálculo de la saliencia. Esta información no se almacena en los nodos de BaseRAW, pues esto obligaría a definir una estructura muy pesada para el tipo nodo y, en realidad, estos datos solo se necesitan para la base o nivel 0 de la pirámide. Es por ello que se crea la estructura de almacenamiento ListaVecinos. Su uso quedará 113
relegada a las funciones EstimarSaliencia, ya en el bloque Determinar ROI. Una vez se dispone del grafo asociado a la base, se procederá a generar la pirámide irregular foveal usando el algoritmo BD3P. La función GenerarPyramid consta de tres partes secuencialmente ejecutadas: la generación de cada uno de los niveles de la jerarquía (GenerarNivel), en un proceso ya descrito en el Capítulo 3, la asignación de un identificador único de clase a cada nodo superviviente del nivel superior de la jerarquía (ActualizarClase), y la transmisión, en un proceso top-down que emplea los enlaces inter-niveles creados por GenerarNivel, del identificador de Clase y del valor de color HSV desde las raíces o padres del nivel superior de la jerarquía hasta la base. Estos datos se actualizan en la pirámide creada, pero la base, representada ahora por un conjunto de regiones o clases (protoobjetos) se graba como BaseSEG. Figura 4-26: Diagrama de secuencia asociado al proceso de segmentación Se aprecia el carácter secuencial del proceso de segmentación de la imagen multirresolución que, como se comentaba al inicio de este apartado, justifica su implementación en la parte software del AP SoC. Aparte del programa principal, 114
cuya actuación seguirá ahora con la estimación de la saliencia y la posición del nuevo foco de atención, sólo los datos almacenados en ListaVecinos y BaseSEG son necesarios pues permitirán la estimación de los mapas de evidencias y saliencia en el bloque Determinar ROI. El diagrama de secuencia de este proceso se muestra en la Figura 4-26. Figura 4-27: Diagrama de secuencia asociado al proceso de estimación de la saliencia y la posición del nuevo foco de atención El proceso se fundamenta ahora en dos funciones principales: EstimarSaliencia, que emplea los datos en BaseSEG y ListaVecinos para computar los contrastes color e intensidad, la redondez y el contraste en orientación, y GenerarParametros, función con la que se cierra el lazo de control del bucle principal, y que estima los valores de los parámetros que definen la retinotopología foveal (T,B,L,R). Al actualizar estos parámetros, el hardware de adquisición de imagen modificará la posición de la fóvea y devolverá una BaseRAW actualizada. Se ha cerrado el bucle principal de funcionamiento. En los siguientes apartados se proporciona información adicional sobre la implementación de estos dos bloques. Comentar que el bloque 115
Visualizador, cuya función es proporcionar un flujo de vídeo a través del conector HDMI de la placa Zedboard, puede intercalarse en cualquier posición de este bucle principal. Como se describió al inicio de este Capítulo, su funcionamiento se tratará de paralelizar con el de los cores principales, pues la generación de una imagen de gran tamaño (1920x1024 si se quiere usar todo el campo del HDMI) es costosa computacionalmente. En futuras modificaciones de la arquitectura propuesta, este bloque de verificación debería sintetizarse en hardware. 4.4.1. Detalles de implementación del algoritmo de segmentación El primero de los problemas que se debe afrontar en el bloque Segmentador BD3P es que el esquema de codificación del grafo no permite una fácil determinación de los vecinos de cada nodo. Esto es, no es fácil conocer los identificadores de los nodos que rodean, en vecindad V-4, a cada nodo. Para resolverlo se recurre al empleo de dos ventanas auxiliares, que irán recorriendo la imagen multirresolución de arriba a abajo para determinar los vecinos de cada nodo. Una de esta ventanas sirve para almacenar toda una fila de posibles vecinos superiores. Su funcionamiento se ilustra en la Figura 4-28. En la esquina superior-izquierda se muestra una imagen multirresolución de dos anillos de resolución y fóvea de 4 x 6 píxeles. En la esquina superior-derecha de la figura se muestra, con un conjunto de flechas, las posiciones en las que se actualizan los valores de esta ventana. En concreto, cuando se almacenan los valores en la posición marcada como A, se almacenan dos valores por nodo. Eso es debido a que la siguiente fila corresponde al siguiente anillo de resolución, y el tamaño de rexel se reducirá a la mitad. Por ejemplo, en el caso del rexel marcado en color verde, se actualizan con el identificador de nodo del rexel las dos posiciones marcadas en verde de la ventana. Los dos réxeles del siguiente anillo de resolución, justamente bajo el rexel verde, podrán ahora comprobar en esta ventana si el rexel verde es su vecino por similitud en color. En ListaVecinos, sin embargo, estas vecindades se almacenarán directamente, al no imponerse restricción por parecido en color. En la posición marcada con B (esquina inferior-derecha), la ventana guarda el identificador de los nodos marcados en rojo y azul. El rexel inmediatamente inferior, de tamaño doble al estar en el siguiente anillo de resolución, puede tener dos vecinos superiores. 116
Figura 4-28: Proceso de almacenamiento de los índices de la representación multirresolución para la estimación de los vecinos superior-inferior (ver texto) Debido a que el esquema de codificación (ver Capítulo 3) emplea el rexel de mayor tamaño de la imagen multirresolución como unidad básica, la segunda de las ventanas sólo tendrá un tamaño igual de dicho rexel (por ejemplo, en el caso mostrado en la Figura 4.25, sería de 4 bits). El esquema se programa en la versión actual de la arquitectura en la parte software, pero su diseño permitirá su sintetizado en la parte lógica, pues las ventanas se podrían mover con la generación del grafo BaseRAW. Sólo el hecho de que en el BD3P la vecindad se haya extendido para implicar también similitud en color dificulta este sintetizado, pues la distancia en color empleada si que resulta compleja de sintetizar. En cualquier caso, queda como trabajo futuro el estudiar si esta estimación de vecinos debe llevarse o no a la parte lógica. Una vez generada la base de la estructura piramidal, la función GenerarNivel permite crear la estructura de enlaces y grafos de dimensiones sucesivamente reducidas que forman la pirámide irregular foveal. En particular, el diagrama de flujo de la primera parte de esta función, encargada de obtener los valores de p y q para cada nodo del grafo de la jerarquía, se muestra en la Figura 4-29. En dicha figura se observa que, tras un primer paso de inicialización de los valores de estas variables para todos los nodos del grafo, se determina primero si el nodo es un mínimo local (tiene un valor de varianza v menor al de sus vecinos). El proceso se complica pues el nodo podría tener un vecino con su mismo valor 117
También se ha detallado el desarrollo de los algoritmos de implementación software que han de ejecutarse en la parte PS del AP SoC, describiéndose el marco completo hardware/software que soporta el sistema completo, definiendo de manera clara dónde se implementa cada uno de los módulos de procesado, y cómo están comunicados entre sí, poniendo especial atención en la transferencia de datos a procesar entre la parte PL y la parte PS. La arquitectura de memoria compartida que facilita esta tarea se ha descrito describiendo su funcionamiento de manera muy esquematizada. 124
Capítulo 5 Pruebas y resultados experimentales Como se esbozó en el Capítulo de Introducción, el sistema propuesto en esta Tesis Doctoral consta de tres módulos básicos: fovealizador, segmentador y estimador de saliencia. Aunque al describir el diseño de estos módulos, en los Capítulos 3 y 4 de la presente memoria, ya se ha proporcionado algún resultado, este Capítulo recoge una descripción más detallada de las pruebas de verificación de estos módulos, así como de los resultados finalmente obtenidos. Es importante notar además que, en cada Sección de este Capítulo, se irá aumentando el nivel de integración. Esto es, el algoritmo de segmentación (Sección 5.2) ya usará el fovealizador para generar el grafo usado en la base de su jerarquía, y el sistema de atención foveal (Sección 5.3) emplea los proto-objetos obtenidos por el segmentador. 5.1. El fovealizador Este módulo agrupa toda la cadena de prepocesado que describimos en el apartado 4.2 del capitulo 4, y que está compuesta por tres etapas: la de interpolación de color, la de generación de niveles multirrresolución y la de conversión de espacio de color. En el modelado y desarrollo de cada una de las etapas se busca cumplir el doble objetivo de conseguir unos resultados de síntesis optimizados en cuanto a recursos utilizados y rendimiento, teniendo en cuenta que deben procesar datos en tiempo real que se suministran en un flujo continuo a razón de un nuevo dato cada ciclo de reloj, además de garantizar la
correcta funcionalidad. Los resultados de síntesis se han agrupado y presentado de manera progresiva para resaltar cómo las directrices de síntesis que se presentaron en las descripciones del Capítulo 4, son fundamentales para conseguir controlar el uso que se hace de los bloques de memoria interna BRAM, y para conseguir que el circuito resultante sea capaz de procesar un nuevo dato cada ciclo de reloj, o lo que es lo mismo, que el Intervalo de Iniciación de los bucles de procesamiento sea igual a 1 ciclo de reloj. La cantidad de Flip-Flop y de LUT nos darán una idea de la complejidad de la lógica necesaria. El correcto funcionamiento de las distintas etapas se ha verificado haciendo uso de un conjunto de imágenes de prueba utilizadas en su trabajo por (Malvar, 2004), tanto a nivel de descripción de alto nivel en C/C++, como a nivel de descripción RTL. 5.1.1. Interpolación de Color La propuesta básica para este bloque contempla trabajar con el tamaño de imagen máximo que suministra nuestro sensor, sin hacer uso de directivas de síntesis, modelando un buffer de línea no optimizado, y sin un procesado particularizado de los bordes de la imagen, utilizando la interpolación básica con una ventana de dimensiones 3x3. DSP 4Clock (ns) 9,40 BRAM_18K 6Latencia máxima (clock cycles) 201739291 FlipFlop 552 Intervalo de Iniciación (clock cycles) 201739292 LUT 895 Interfaz ap_memory Tabla 5-1: Recursos utilizados por la implementación de la propuesta básica Cada una de las tres líneas que componen el buffer de línea requiere de 2 BRAM para poder almacenar una línea completa de la imagen original (2592 píxeles), lo que significa que uno de estos bloques está infrautilizado, pues sólo estamos usando menos de la mitad de su capacidad. Sería interesante analizar los requisitos del sistema por si fuera suficiente trabajar con una imagen de menor longitud de línea. Los array de datos de entrada y salida de la función principal se implementan con un interfaz de acceso a memoria lo que requiere también de lógica adicional a la necesaria para el propio procesamiento. El procesamiento se realiza en esta propuesta básica de manera secuencial, lo que hace necesario 126
unos 2 segundos para procesar completamente una imagen. Hay por lo tanto dos aspectos que hay que controlar: el tipo de interfaz, pues el bloque tiene que procesar datos tipo stream, y hay que mejorar el rendimiento explotando el paralelismo que ofrece la FPGA. Propuesta básica + Pipeline Bucle + Interfaz Stream DSP 453 BRAM_18K 666 FlipFlop 552 479 500 LUT 895 572 543 Clock (ns) 9,40 9,40 9,40 Latencia máxima (clock cycles) 201739291 5043393 5043391 Intervalo de Iniciación (clock cycles) -- 1 1 Interfaz ap_memory ap_memory axis Tabla 5-2: Comparación resultados con mejora en rendimiento y definición de interfaz Forzando a la herramienta de síntesis a implementar el bucle principal de procesado con una arquitectura pipeline se obtiene el rendimiento máximo que nos permite procesar una nueva entrada en cada ciclo de reloj. Cuando además definimos el tipo de entrada/salida para que sea de tipo stream, se obtiene una simplificación en la lógica de control de dicho interfaz reflejada en una reducción de los recursos utilizados Esta implementación representa la propuesta básica definitiva, sobre la que se ha realizado diversas variaciones buscando mejoras funcionales manteniendo el nivel de optimización de recursos. 5.1.1.1. Ajuste entre ancho de imagen y tamaño de BRAM No siempre nuestra aplicación de segmentación requiere la máxima resolución de 5 megapíxeles que ofrece nuestro sensor, por lo que podemos reducir el ancho de la imagen original para que la anchura del buffer de línea coincida con la dimensión máxima que se puede implementar en un solo BRAM (en nuestro caso 2Kx8). Esto nos lleva a trabajar con una imagen de 3 megapíxeles (2048x1536), dimensionado que supone una reducción en la 127
cantidad de recursos necesarios, especialmente llamativo en el número de BRAM necesarios. 5.1.1.2. Optimización del buffer de línea En el capítulo 4 ya se justificó que no es realmente necesario utilizar un buffer de línea completo de dimensiones N x MAXCOLS, pues el procesamiento de cada ventana no exige que la última línea del buffer esté completa, por lo que realmente sólo son necesarias N-1 líneas. De esta manera la ventana de procesado se “rellena” en sus N-1 primeras filas con valores que proceden del buffer de línea, y su fila N se rellena directamente con datos que proceden de la imagen original. Propuesta básica Ajuste Imagen/BRAM Buffer de línea optimizado DSP 33 3 - 3 BRAM_18K 63 4 - 2 FlipFlop 500 495 520 - 514 LUT 543 538 557 - 552 Clock (ns) 9,40 9,40 9,40 Latencia máxima (clock cycles) 5043391 3149319 5043391 - 3149319 Intervalo de Iniciación (clock cycles) 11 1 Interfaz axis axis axis Tabla 5-3: Comparativa resultados con ajuste de dimensiones y buffer de línea optimizado El ajuste de tamaños entre la imagen y los BRAM supone un ahorro del 50% de estos recursos, y una ligera reducción en la lógica de control de los mismos. La columna de resultados para el buffer de línea optimizado, recoge estos tanto para el caso de imagen original e imagen ajustada en tamaño. Puede llamar la atención la reducción en la latencia máxima, pero este valor es básicamente la resolución de la imagen procesada. Lo realmente importante es que el rendimiento se mantiene siempre en un ciclo de reloj por cada dato procesado. 5.1.1.3. Interpolación adaptativa En el capítulo 4 se presentó una variante a la interpolación bilineal básica que ofrece una mejora en la calidad de la imagen reconstruida, a costa de una 128
estructura de datos algo más compleja pues requiere de una ventana de procesado de dimensiones 5 x 5 por lo que el buffer de línea debe tener dimensiones de 5 x MAXCOL o 4 x MAXCOL si se opta por el buffer de línea optimizado. 5.1.1.4. Procesado de los píxeles del borde de la imagen En el procesado de imágenes basado en una ventana centrada en el píxel actual que procesamos, siempre que se procesa los píxeles correspondientes al borde de la imagen, la ventana de procesado está incompleta. En la propuesta básica los datos que faltan están inicializados a 0, pero el tipo de procesado es el mismo que en los píxeles internos donde sí se dispone de la ventana completa. Esto implica la obtención de resultados erróneos para todos los píxeles del borde. La particularización del procesado en esta situación para obtener resultados correctos, implica mayor complejidad en la lógica de control y mayor número de recursos de procesado. Propuesta básica Procesado de Bordes Interpolación adaptativa DSP 366 BRAM_18K 6610 FlipFlop 500 620 638 LUT 543 580 593 Clock (ns) 9,40 9,40 9,40 Latencia máxima (clock cycles) 5043391 5043391 5043391 Intervalo de Iniciación (clock cycles) 111 Interfaz axis axis axis Tabla 5-4: Comparativa resultados con procesado particular en los bordes y con interpolación adaptativa frente a bilineal básica. 5.1.2. Verificación funcional y RTL Las imágenes de prueba originales tienen un formato de color RGB888, y a partir de ellas se ha generado un imagen que representa el mosaico de bayer a partir del cual se realizará la reconstrucción de la información de color para cada píxel. 129
a1) imagen original b1) imagen original c1) imagen original a2) mosaico bayer b2) mosaico bayer c2) mosaico bayer a3) resultado interpolación b3) resultado interpolación c3) resultado interpolación Figura 5-1: Resultados de la reconstrucción por interpolación bilineal Los resultados muestran el correcto funcionamiento del proceso de reconstrucción, tanto en imágenes con figuras de tamaño reducido (caso de las vallas en la columna de la izquierda), como en imágenes con objetos en primer y segundo plano así como en imágenes en con objetos originalmente con bordes bien definidos. En este último caso se puede observar el efecto zipper típico en este tipo de reconstrucción de color. 130
5.1.3. Generación de niveles multirresolución La propuesta básica para el módulo generador de los niveles multirresolución procesa datos de 8 bit en un flujo continuo y genera a su salida 5 niveles de resolución decreciente. Internamente está modelado como un datapath de aritmética entera para datos de anchura fija definida por el tipo estándar de C/C++ unsigned short, que es utilizado por ser el de tamaño más aproximado a los datos a procesar. El datapath no trunca los valores intermedios por lo que la anchura del mismo se va adaptando a medida que generamos los niveles de menor resolución. Propuesta básica Pipeline bucle principal Interfaz Stream DSP 560 BRAM_18K 666 FlipFlop 513 419 409 LUT 457 419 414 Clock (ns) 7,50 9,09 5,42 Latencia máxima (clock cycles) 45353520 5038860 5038861 Intervalo de Iniciación (clock cycles) ?11 Interfaz ap_memory ap_memory axis Tabla 5-5: Resultados de síntesis de la propuesta básica para uno solo de los canales de color. Los recursos totales necesarios son los equivalentes a tres canales como el ilustrado en esta tabla. El rendimiento óptimo de una dato procesado por cada ciclo de reloj se consigue, una vez más, forzando la implementación de una estructura pipeline para el procesamiento modelado en el bucle principal. El interfaz necesario para su integración a nivel de sistema se garantiza forzando el tipo STREAM para las entradas y las salidas. Muy interesante el informe detallado sobre el uso que se hace de los bloques de memoria y que se resume en la siguiente tabla, en la que cada una de las líneas recoge la información de relacionada con los buffer necesarios en la generación de cada nivel. 131
Memoria BRAM_18K Words Bits LineBuffer1 2 1296 16 LineBuffer2 1 648 16 LineBuffer3 1 324 16 LineBuffer4 1 162 16 LineBuffer5 18117 Tabla 5-6: Uso de los recursos BRAM con una anchura de datapath para unsigned short Podemos observar que la herramienta HLS no optimiza la anchura del tipo de datos utilizado, forzando la creación de estructuras de, como mínimo, la del tipo base unsigned short de 16bit. Sin embargo si la adapta para representar datos que requieran más anchura, como ocurre en el buffer utilizado en la creación del nivel 5 de resolución. Todos los bufferes encajan dentro de un solo BRAM excepto el primero que requiere de dos bloques. Esto es debido a que, como se describió en el capítulo 3, entre las configuraciones posibles de los BRAM estaban la de 2048x8 (o bien 2048x9), pero para una anchura mayor ya debemos usar 1024x16, con una profundidad insuficiente para dar cabida a las 1296 palabras necesarias. 5.1.3.1. Ajuste anchura de datapath mediante uso tipos arbitrarios Cuando se hace necesario la optimización de la anchura de datos en el modelado del datapath, el entorno de desarrollo de la herramienta HLS nos ofrece la posibilidad de utilizar tipos predefinidos no estándar que nos permiten definir la precisión de los datos de tipo de entero, ajustándose a la anchura que realmente necesitamos en nuestro procesado, forzando al proceso de síntesis a generar la lógica necesaria con esas mismas dimensiones. Es un aspecto importante porque son muchos los registros internos que se generan cuya dimensión depende estrechamente del tipo de dato con el que se trabaja. La segunda columna de resultados de la Tabla 5-8 así lo refleja, en una reducción importante del número de Flip-Flop necesarios para implementar estos recursos. Este ajuste del tipo de datos también afecta al número de bloques BRAM necesarios para implementar el buffer de mayor tamaño que es el necesario en la generación del nivel 1. Como podemos ver en la Tabla 5-7 el análisis de los requisitos de memoria para este buffer muestra que ahora solo son necesarias palabras de 9 bit, lo que nos permite encajar esta estructura en un solo bloque BRAM de dimensión 2048x9. El resto de buffers tiene 132
dimensiones menores, y aunque la anchura de dato es creciente en los diferentes niveles, todas ellas encajan en bloque de BRAM de 1024x17 Memoria BRAM_18K Words Bits LineBuffer1 112969 LineBuffer2 164811 LineBuffer3 1 324 13 LineBuffer4 1 162 15 LineBuffer5 18117 Tabla 5-7: Uso de los recursos BRAM con una anchura de datapath ajustada mediante el uso de tipos de precisión arbitraria en función de la etapa del datapath modelada. 5.1.3.2. Optimización de uso de bloques BRAM por fusión de memorias Otro aspecto interesante en los datos recopilados en la Tabla 5.7 es que, excepto el buffer necesario para el nivel 1, el resto requiere de un número de palabras bastante reducido, pero a pesar de ello la herramienta HLS le asigna un bloque BRAM de 1024 palabras con un desaprovechamiento importante de la capacidad de dichos bloques. El proceso de síntesis por defecto no garantiza esos niveles de optimización, que solo se pueden explorar haciendo uso de las directivas disponibles en relación con la implementación de estructuras de memoria. Entre esas directivas disponemos de la posibilidad de definir arrays de memoria grandes a partir de arrays más pequeños, por los que podemos unir, por ejemplo, los buffers de los niveles 2 y 3 por un lado, y los de los niveles 4 y 5 por otro. En cada uno de los casos, el resultado encaja en un solo bloque de 1024 palabras. 133