´ DE INGENIER´IA ELECTRICA, ´ XVI CONVENCION CIE-2015
1
Detecci´on de bordes Usando una Cell Matrix con una Nueva Arquitectura de C´elula (Edge Detection Using A Cell Matrix With A Novel Architecture Of Cell) Andr´es C. Jim´enez y John P. Anzola
Resumen—This paper develops an application for the Cell Matrix based on a modified PIG (Processing Integrated Grind) structure for detecting edges in images of different dimensions, creating eight different outcomes in a single processing cycle per pixel in a binary image, without using convolutions with masks. Palabras Claves—Cell Matrix, Edge detection, FPGA, PIG, Reconfigurable Hardware.
´ I. I NTRODUCCI ON La detecci´on de bordes en im´agenes permite detectar los cambios bruscos en la intensidad o el cambio en brillo de la imagen, reduciendo la cantidad de informaci´on a procesar. Existen t´ecnicas para la detecci´on de bordes tales como cruce por cero, diferenciaci´on, Sobel y Canny, las cuales utilizan matrices (mascaras) como base para realizar la convoluci´on o correlaci´on sobre los pixeles de la imagen para detectar bordes, por lo cual, utilizan multiplicaciones y sumatorias aumentando el tiempo de c´omputo, y en algunos casos para resaltar los bordes, es necesario utilizar operadores morfol´ogicos como la dilataci´on. El objetivo es usar las c´elulas de la Cell Matrix en el proceso de detecci´on de bordes para reducir el tiempo de c´omputo detectando bordes y al mismo tiempo resaltandolos[1][2]. II. C ELL M ATRIX La Cell Matrix es un sistema bio-inspirado reconfigurable sin s´uper estructuras1 , el cual logra resolver problemas que requieran un gran paralelismo en un menor tiempo que los sistemas que est´an compuestos por s´uper estructuras. El modelo de c´elula que se usa para el dise˜no de la Cell Matrix es el modelo PIG, en donde su RTL (Register Transfer Level) se describe en la Figura 1 [3][4].
Fig. 1.
Arquitectura c´elula PIG
En la Figura 2, se muestra como es configurada una c´elula usando el modelo PIG al extremo de una Cell Matrix de 1x3; 1 Sistemas que est´ an compuestos por bloques de memoria, ALU’s y bloques de interconexi´on.
en el primer paso, la c´elula X carga la SLUT de la c´elula Y con los valores π1 , actuando la c´elula Y como una uni´on directa de configuraci´on entre la c´elula X y la c´elula Z, logrando con esto que la c´elula X pueda cargar un valor deseado π2 en la c´elula Z, en este proceso la c´elula Y se llama “Code data duality”o CDD por estar funcionando en modo de datos y a la vez enviando c´odigo a la c´elula vecina. Este proceso solo logra configurar la c´elula adyacente, con lo cual a medida que el arreglo de c´elulas aumenta, las etapas de configuraci´on aumentan (cada etapa son 128 ciclos de m´aquina), aumentando la dificultad de configuraci´on y el numero c´elulas que se usan para el control de programaci´on como las CDD [3], con lo cual se pierden c´elulas para el procesamiento de datos. Por otro lado, utilizando el modelo de programaci´on con la c´elula CDD, la c´elula que est´a al extremo ya configurada puede modificar a cualquier c´elula vecina dada su SLUT, haciendo colisi´on de datos sobre la c´elula que se encuentra en programaci´on [4].
Fig. 2.
Configuraci´on de una c´elula no adyacente [8]
El modelo de c´elula que se usa para el dise˜no de la Cell Matrix en este paper es el modelo PIG modificado, el cual, usa la salida del dato de la SLUT para enviar el valor antiguo de la tabla interna al bit de salida de la cara de la c´elula, en donde el bit de control de entrada este activo. Este bit de salida puede ser aprovechado para enviar los datos de programaci´on a la siguiente c´elula. Para esto, se hace necesario que los datos de programaci´on se env´ıen por la cara adyacente de la c´elula por la cual est´en ingresando los datos de programaci´on (ver Figura 3), logrando reducir los ciclos de m´aquina para programar un arreglo de c´elulas. Esta modificaci´on se desarrolla a partir de un circuito que programe a la c´elula con una se˜nal externa, y por medio de la entrada de datos en una de sus caras ingresen los valores de programaci´on. Adem´as, es necesario interconectar la salida de la cara opuesta en la salida de la SLUT sin usar s´uper estructuras, proponiendo la arquitectura mostrada en la Figura 4. Las c´elulas PIG modificadas a diferencia del modelo original presentan tres modos de funcionamiento, el modo de datos, el modo de control y el modo de programaci´on general; cuando la c´elula no tiene en alto ning´un bit en el puerto de entrada de control ni en el de programaci´on general, se dice que la c´elula est´a funcionando en modo de datos, enviando a sus salidas, en forma asincr´onica los valores que
´ DE INGENIER´IA ELECTRICA, ´ XVI CONVENCION CIE-2015
est´en configurados en su SLUT2 . Pero si la c´elula tiene al menos en uno de sus puertos de entrada un bit en alto de control y en bajo el bit de programaci´on general, la c´elula entra inmediatamente en modo de control, por lo que el bit de datos de entrada ubicado en la cara donde el bit de configuraci´on est´a en alto, configura nuevamente la tabla de la verdad de la c´elula por medio de bitstream (env´ıo serial de los bits de programaci´on), esto se hace por medio del sincronismo de un reloj global. En caso contrario en el cual el bit de programaci´on general este activo, la SLUT de la c´elula se configura por medio de los valores que ingresen por la cara norte, y los datos que estaban en la SLUT se env´ıan por el bit de salida de datos en la cara sur [4][5][6].
Fig. 3.
2
Fig. 5.
Matriz de transici´on c´elula PIG modificada
‘0’ l´ogico. En el caso que se desee aumentar la velocidad de procesamiento se hace necesario dise˜nar un arreglo de c´elulas igual al tama˜no de la imagen e implementarla directamente en hardware (ver Figura 6).
MOdelo envio de datos de la SLUT a la c´elula adyacente Fig. 6.
Barrido C´elula PIG modificada sobre una imagen de 6x6
La ecuaci´on 1 describe el comportamiento de la matriz de transici´on de la c´elula, donde el dato de entrada solo depende de los 4 valores que tengan los bits en las entradas de datos en las caras, para lo cual la cara norte se le asigna un peso de 8, a la cara sur de 4, a la cara oeste de 2 y a la cara este de 1. Fig. 4.
(Salidan | Din = x) = Z+ ≤ 1 ∪ {0}
Arquitectura c´elula PIG modificada
´ DE B ORDES CON LA C ELL M ATRIX III. D ETECCI ON La SLUT de la c´elula PIG modificada se puede representar como una matriz de transici´on reconfigurable de 16 entradas con 8 salidas independientes (ver Figura 5). Cada salida tanto de datos como de control es usada para almacenar los resultados de la detecci´on de bordes, generando en la salida 8 resultados de forma simult´anea, ayudando a la separaci´on de diferentes caracter´ısticas de la imagen en un solo proceso, lo cual, diferencia este m´etodo de los tradicionales que necesitan implementar la convoluci´on de una m´ascara (la cual depende del m´etodo a usar) con la imagen a procesar generando un solo resultado por proceso[7]. Con el fin de ahorrar recursos, el m´etodo hace uso de solo una c´elula PIG, la cual, es trasladada pixel a pixel en una im´agen en blanco y negro, en donde, el color blanco se toma como un ‘1’ l´ogico, mientras que el negro se toma como un 2 Shiftable Lock-Up Table o SLUT, Es una arquitectura de hardware reconfigurable en circuitos digitales, la cual describe una LUT por medio de registros de corrimiento y es representada como una memoria RAM
(1)
siendo: n : tipo de salida; x = Dn ∗ 8 + Ds ∗ 4 + Dw ∗ 2 + De . En el caso de la Figura 7, se tiene que la cara norte y este tienen un ‘1’ l´ogico en la entrada, lo cual genera la equaci´on 1: Din = 8 ∗ 1 + 4 ∗ 0 + 2 ∗ 0 + 1 ∗ 1 = 9
Fig. 7.
(2)
C´elula PIG modificada con datos en la entrada norte y este
Los datos de entrada en la matriz de transici´on se pueden tomar para detectar diferentes tipos de bordes como se aprecia
´ DE INGENIER´IA ELECTRICA, ´ XVI CONVENCION CIE-2015
3
en la Figura 8, si se quieren detectar bordes verticales la c´elula debe detectar un ‘1’ l´ogico en la cara este con su complemento en la cara oeste y lo mismo en caso contrario en donde se detecte un ‘1’ l´ogico en la cara oeste (Figura 8b.), en los dem´as casos como en los bordes verticales se debe detectar un cambio entre la cara norte y la cara sur como se aprecia en la Figura 8c, y en los bordes diagonales se deben detectar cambios entre sur-oeste, sur-este, norte-este y norte-oeste ver Figura 8a y 8d.
Fig. 10. (a) Detecci´on de bordes usando la c´elula modificada (b) Detecci´on de bordes horizontales usando la c´elula modificada
Fig. 8. Detecci´on de bordes usando la C´elula PIG modificada (A) y (D) bordes diagonales (B) bordes verticales y (C) bordes horizontales
Matriz produce 8 resultados en un solo proceso realzando mejor los bordes sin usar operaciones morfol´ogicas, mientras que el filtro Laplaciano muestra los bordes muy suaves los cuales tienen que utilizar operaciones morfol´ogicas para realzar su resultado como se evidencia en la Figura 11. Al evaluar el tiempo de computo de una c´elula modificada sobre un kit de desarrollo DE2 de Terasic-Altera, dio un retardo entre entrada y salida critico de 8.897ns, dando como resultado una operaci´on de 112.39x106 pixeles analizados por segundo por c´elula (ver Figura 12), lo cual, si se usa una c´elula por pixel es posible analizar 112.39x106 im´agenes por segundo.
IV. R ESULTADOS El m´etodo para la detecci´on de bordes es simulado en Octave usando como base la imagen mostrada en la figura 9, la cual, presenta bordes suaves diagonales, bordes horizontales y bordes fuertes verticales. La ecuaci´on 3 es usada en la salida de control norte en la matriz de transici´on de la c´elula para detectar todos los bordes de la imagen binaria. DOutCN = 1 | Din
+
∈ Z ≤ 14 ∪ {0}
(3)
Fig. 11. (a) Figura original (b) Imagen filtrada con un filtro Laplaciano (c) Imagen filtrada con la Cell Matrix
Fig. 12. Respuesta de tiempos entrada y salida de la c´elula en un kit de desarrollo DE2 Fig. 9.
Imagen base para detectar bordes
V. C ONCLUSIONES El resultado al procesar la imagen en la salida de control norte de la c´elula es mostrado en la Figura 10a, en donde se puede apreciar los diferentes bordes de la imagen, pero en el caso que se procese la imagen con la ecuaci´on 4, la cual es almacenada en la matriz de transici´on de la salida de control sur, se detectan bordes verticales como se aprecia en la Figura 10b. DOutSN = 1 | (Din = 4)
(4)
Este m´etodo al ser implementado de forma secuencial consume mayores recursos computacionales que los m´etodos tradicionales que usan mascaras para la detecci´on de bordes, pero al comparar el resultado de un filtro Laplaciano, la Cell
El modelo m´as utilizado para el desarrollo de la c´elula en la Cell Matrix es el modelo PIG, por su f´acil dise˜no, uso y su descripci´on en HDL. Pero al configurar una c´elula al extremo de un arreglo, necesita configurar las c´elulas en modo CDD, lo cual hace que la programaci´on se demore m´as tiempo. Para solucionar este inconveniente se introdujo una tercera forma de operaci´on de la c´elula que se denomin´o en este art´ıculo como el modo de programaci´on general, que permite la programaci´on de toda una Cell Matrix, en lo que el modelo PIG se demora en configurar solo una c´elula al extremo del arreglo. La Cell Matrix se puede usar para la detecci´on de bordes en paralelo, reduciendo el tiempo de c´omputo al poder dar
´ DE INGENIER´IA ELECTRICA, ´ XVI CONVENCION CIE-2015
8 resultados diferentes de forma simult´anea y al mismo tiempo resaltando los bordes de forma significativa sin utilizar operadores morfol´ogicos como dilataci´on y erosi´on durante el proceso, adem´as, al hacer uso de la nueva arquitectura de la c´elula PIG, se logra reducir los ciclos de programaci´on, permitiendo cambiar las operaciones de filtrado en el mismo tiempo que la c´elula PIG se demora en solo configurar una c´elula a un extremo del arreglo. Las im´agenes trabajadas se manejan solamente en binario reduciendo el tama˜no de la c´elula de la Cell Matrix, en caso de querer trabajar con im´agenes en escala de grises la c´elula debe aumentar el n´umero de bits en sus entradas y salidas para tener mayor resoluci´on. En este paper solo se utiliza una c´elula para el procesamiento de detecci´on, lo cual aumenta el tiempo de procesamiento pero reduce el espacio que ocupa en hardware. La Cell Matrix es una arquitectura que permite el desarrollo de Hardware evolutivo (EH), al ser una arquitectura que se puede reconfigurar por ella misma dependiendo de los estados internos o externos. Una de las opciones para la modificaci´on de la c´elula en el uso de la Cell Matrix en EH, es implementar un m´etodo de inicializaci´on o de configuraci´on aleatorio de la SLUT para la tarea de mutaci´on. Se sugiere empezar con un m´etodo sencillo como el m´etodo de Lehmer, que ocupa muy pocos recursos para su implementaci´on en hardware, debido a que la operaci´on modulo se puede describir con sumatorias al ser el operando un n´umero par [9], [10], [11], [12], para luego aplicar un m´etodo totalmente aleatorio y as´ı analizar los resultados y compararlos con otras arquitecturas en las que se pueda desarrollar hardware evolutivo. R EFERENCIAS [1] W. Gao, X. Zhang, L. Yang, and H. Liu, An improved Sobel edge detection, Computer Science and Information Technology (ICCSIT), vol. 5, no. 3rd IEEE International Conference on (ICCSIT), pp. 67,71, 9-11 July 2010. [2] J. Shang and F. Jiang, An algorithm of edge detection based on soft morphology, IEEE 11th International Conference on Signal Processing (ICSP), no. 1,1, pp. 166,169, 21-25 Oct 2012. [3] Lukas Sekanina, Evolvable Components, From Theory to Hardware Implementations.: Springer, 2004. [4] L. Durbeck, N. J. Macias, The Cell Matrix: An Architecture for Nanocomputing, in Eighth Foresight Conference on Molecular Technology, Bethesda, Maryland, 2000, pp. 217-230. [5] L. K. Durbeck, N. J. Macias, A Hardware Implementation of the Cell Matrix Self-Configurable Architecture: The Cell Matrix MOD 88TM, IEEE Computer Spciety, 2005. [6] N.J. Macias and P.M. Athanas, Application of Self-Configurability for Autonomous, Highly-Localized Self-Regulation, in Adaptive Hardware and Systems, 2007. AHS 2007. Second NASA/ESA Conference, 2007, pp. 397-404. [7] N.J. Macias, Ring Around the PIG: A Parallel GA With Only Local Interactions Coupled With a Self-Reconfigurable Hardware platform to Implement an O Evolutionary Cycle for Evolvable Hardware, From Proceedings of the 1999 Congress on Evolutionary Computation IEEE.(1999) [8] Nicolas J Macias, The PIG paradigm: The desing and use od a massively parallel fine grained Self-Reconfigurable infinitely scalable architecture, IEEE, 1999. [9] Rabung J. R. , Bogyo t. P., Payne W. H.: Coding the Lehmer Pseudorandom Number Generator: vol. 12 no. 2 (1969) [10] Yong L., Higuchi X. , Evolvable Hardware.: Springer, 2006. [11] Agoston E., Smith J. E.: Introduction to Evolutionary Computing: Natural Computing Series Springer (2010) [12] Butler J. T., Sasao T.:Fast Hardware Computation of x mod z: IEEE (2011)
4
Andr´es Camilo Jim´enez Alvarez Docente del programa de Ingenier´ıa Electr´onica de la Fundaci´on Universitaria Los Libertadores, MsC. en Ingenier´ıa Electr´onica de la Pontifica Universidad Javeriana, actualmente se encuentra cursando el primer a˜no del Doctorado en Ingenier´ıa de la Universidad Distrital Francisco Jos´e de Caldas, Bogot´a D.C., Colombia. Es integrante de los grupos de Investigaci´on GUIAS y LIDER.
[email protected]
John Petearson Anzola Docente del programa de Ingenier´ıa Electr´onica de la Fundaci´on Universitaria Los Libertadores, MsC en Ciencias de la Informaci´on y las Comunicaciones de la Universidad Distrital Francisco Jos´e de Caldas, actualmente se encuentra cursando el primer a˜no del Doctorado en Ingenier´ıa de la Universidad Distrital Francisco Jos´e de Caldas, Bogot´a D.C., Colombia. Es integrante de los grupos de Investigaci´on GUIAS y GICOECOL.
[email protected]
