Synthetic generation of address-events for real-time image processing

Synthetic Generation of Address-Events for Real-Time Image Processing A. Linares-Barranco, R. Senhadji-Navarro, I. Garcia-Vargas, F. Gomez-Rodriguez, G. Jimenez and A. Civit. Arquitectura y Tecnologia de Computadores. Universidad de Sevilla. AV. Reina Mercedes sin, 41012-Sevilla SPAIN Absnacf - Address-Event-Representation (AER) is a stream. The receiver pixel integrates the pulses and commnnicatlon protocol that emulates the nenons system’s reconstmcts the original low frequency COntinUOUS-time neurons communication, and that is typically used for waveform, like a neuron does in the nervous system. Pixels transferring Images between chips. It was originally developed that are more active are accessing the bus more frequently for bio-inspired and real-time image processing systems. Such than those less act,ve. systems may consist of a complicated hierarchical strnctnre ~~~~~~i~~i~~ the addresses performing exba operations on the images while they travel from one chip to with many chips that transmit Images among them in real time, while performing some processing (for example, convolutions). streams from images stored in a computer’s memory are (le. EEPROM) allows transformation (ie. shifting and presented. A hardware version will work in real-time. ~11 of rotation) of images. Also, the image transmitted by one chip them have been evaluated and compared. can be received by many receiver chips in parallel, by properly handling the asynchronous communication protocol. The peculiar nature of the AER protocol also 1. INTRODUCTION allows for very efficient convolution operations within a 1991 by Sivilotti [SI for transferring the state of an array of There is a growing community of AER protocol users for analog time dependant values from one chip to another. It bio-inspired applications in vision and audition systems, as uses mixed analog and digital principles and exploits pulse demonstrated by the success in the last years of the AER density modulation for coding information. Fig. 1 explains group at the Neuromorphic Engineering Workshop series the principle behind the AER basics. [I]. The goal of this community is to build large multi-chip and multi-layer hierarchically structured systems capable of performing complicated array data processing in real time. The success of such systems will strongly depend on the availability of robust and efficient development and debugging AER-tools. One such tool is a computer interface that allows not only reading an AER stream into a computer and displaying it on its screen in real-time, but also the opposite: from images available in the computer’s memory, In this paper severa] software methods for generating AER another’ For properly coded memories Address-Event-Representation (AER) was proposed in receiver chip [81. [U ’ generate a synthetic AER stream in a similar manner as would do a dedicated VLSI AER emitter chiu 121141151161. Fig. 1: lllustmlion of AER infci-chip communicrfion scheme The Emitter chip contains an array of cells (like, for example, a camera or artificial retina chip) where each pixel shows a continuously varying time dependant state that changes with a slow time constant (in the magnitude order of milliseconds). Each cell or pixel includes a local oscillator (VCO) that generates digital pulses of minimum width (a few nanoseconds). The density of pulses is proportional to the state of the pixel (or pixel intensity). Each time a pixel generates a pulse (which is called “event”), it communicates to the array periphery and a digital word representing a code or address for that pixel is placed on the external inter-chip digital bus (the AER bus). Additional handshaking lines (Acknowledge and Request) are also used for completing the asynchronous 1 . _I .. .. ~ This work is involve in the framework of the European Research project CAVIAR, one of the objectives of CAVIAR is develop an AER-computer interface. This paper presents several methods for synthetic AER streams generation (section 11). It also evaluates these methods attending to the execution time comparison and to the error of distribution of the events along the time associated to an image: distance to the frequency of an intensity level. The methods are evaluated for images with different average intensity levels with a Gaussian histogram (from IO-90% charge of events) and for a typical image (around 50 % charge of events) (section 111). Conclusions presented in this paper are not definitive. A hardware implementation and its study is necessary for a real-time comparison. communication. The inter-chip AER bus operates at the maximum possible speed. In the receiver chip the pulses are 11. SYNTHETIC STREAM GENERATION directed to the pixels or cells whose code or address was on the bus. This way, pixels with the same code or address in the emitter and receiver chips There are many software to transform a the Same pulse bitmap image into an AER stream of pixel addresses. In all 0-7803-7937-3/03/$17.00 02003 IEEE 462 of them the frequency of appearance of the address of a This method can be enhanced by applying a small shift given pixel must be proportional to the intensity of that before placing the events in the time period. This shift can pixel. Note that the precise location of the address pulses is he the address of the pixel. For example, the pixel not critical. The pulses can be slightly shifted from their (i,j)=(lO,lO) will be shifted 1290 positions respect to the nominal positions; the AER receivers will integrate them to beginning of the time period (N=M=I28). These positions recover the original pixel waveform. The hardware implementation of this method is under addresses that will he sent to an AER receiver chip via an study. Bul, the time period is not generated sequentially, so, AER bus. If we have an image of NxM pixels and each pixel the first implementation seems to need a memory to save the can have a grey level value from 0 to K, one possibility is to complete time period before transmitting it. place each pixel address in the address sequence as many times as the value of its intensity, and distributed in D. TheRandom method are translated as a delay in the transmission of the event. Whatever algorithm is used, it will generate a vector of equidistant position. In the worst case (all pixels with value This method places the address events in the slot e, the address sequence would be filled with NxMxK positions obtained by a pseudo-random number generator based on Linear Feedback Shift Registers (LFSR) [71[9]. addresses. The time used for transmitting an image needs to be the same for any image intensity charge, leaving blank Due to the properties of the LFSR used, each slot position is slots if non-event has to he sent. Each algorithm would generated only once and no collisions appear. If a pixel in implement a particular way of distributing these address the image has the intensity p, then the method will take p events. Let us propose some algorithms: the Scan method, the Scan Slice, the Uniform method, the Random method, values from the pseudo-random number generator and places the pixel address in the corresponding p slots of the the Random-Square method and the Exhaustive method. address sequence. They will not be equidistant but will appear along the complete address sequence. This method is fast, because the image is swept only once, and because the In this method the image is scanned many times. For each algorithm does not need to perform searches for empty Slots. scan, every time a non-zero pixel is reached its address is Due to the LFSR can obtain two consecutive, or very put on the address sequence in the first available slot, and closer, addresses in a few calls, The LFSR-based method the pixel value is decremented by one. This method is very can be enhanced using a b-bit counter for the high part Of fast, due to it does not need to look for empty slots, although the address. So, for each call to the address generator, 2' the image needs to be scanned many times (K times in the addresses equally distributed are obtained. For pixels with a worst case). However, a non-well event distribution is grey level value near to 2', the distribution obtained is obtained due to all pulses of the pixels with low intensity similar to the ideal distribution. However, for different grey values will appear only at the beginning of the sequence. level, the distribution of the events gets worse again. Tuning the correct size counter value for each image, the random B. The Scan-Slice method method could be improved. A. The Scan method Fig. 2 shows the LFSR stmctllre with a 2-bit counter for a 128x128 images with a 256 grey levels. The Scan method can be enhanced in the distribution of events if an blank slot is left when all the events for a pixel LSB .>21 have been sent. The image is scanned many times, as the h,SB L FIR Scan method does, hut when a pixel's value is zero, a blank "f-1 '7 ''1 ''1 "1 7 1 '1 7 7 I I I I y slot IS left in the time period. --- I I - Both the Scan method and the Scan-Slice method can be easily implemented in hardware, because the time period is generated sequentially. So, the required hardware could be a memory for store the image, plus the control circuitry C. The UniJorm nielhod Fig. 2: LFSR with a 2-bit counter for pseudo-random numbers generation. E. The Randoni-Square method Using the Random method with a fixed size counter from In this method, the image is scanned pixel by pixel only I to the maximum grey level, the event distribution for high once. For each pixel, the generated pulses must be level pixels is acceptable, but poor for low level values. distributed at equal distances. As the sequence is getting Substituting the counter by another LFSR, the distribution filled, the algorithm may want to place addresses in slots could he improved. that are already occupied. This situation is called 'collision' For a 128x128 image with maximum grey level of 255, and it appears with the AER approximation of inter-chip 8-bit LFSR (LFSR-8) is used for selecting 255 slices of communication. In this case, it will put the pulse in the 128x128 positions. and another 14-bit LFSR (LFSR-14) nearest empty slot of the time period. So, this method, selects the position inside the slice. The image is scanned apparently, will make more mistakes at the end of the only once. For each pixel a 14-bit number is generated by process than the beginning. The execution time grows the LFSR-14, and the LFSR-8 is called as many times as the considerably because the collisions have a high-cost in time intensity level of the pixel would indicate. Fig. 3 shows the to resolve it. LFSRs used by the Random-Square method. 463 mlm7 h,SB LNR-8 “R-I, LSB Fig. 3: LFSR-8 and LFSR-I4 used by the Random-Square method. F. The Exhaustive method This algorithm also divides the address event sequence in K slices of NxM positions for an image of NxM pixels with a maximum grey level of K. This method is based on the idea that each possible event (as maximum NxMxK) has assigned one fixed position in the address event sequence. In such way, for the slice k, an event of the pixel (i,j) is sent on the time f if the following condition is asserted: (k. c.,j)mod K + c,j 2 K N, M .(k -l)+ (i - I) .M + j = I where c,j is the intensity value of the pixel 0,j) (see Fig. 4). and N.M K Fig. 5: Test image set (10% to 90% event charge) All of the methods have been implemented in C++ language and an application has been developed which allows the generation of the address events from a greyscale image and calculate the parameters previously described. The Fig. 6 shows the screenshot of this software interface. Fig. 4 The event distribution made by the Exhaustive muthad. The Exhaustive method tries to distribute the events of each pixel into the K slices at equal distances. For this propose, the algorithm scan the image K times. In the iteration k, if the previous condition is true, then the corresponding event is sent, otherwise the algorithm will wait for the following event (no event is sent in time r). Ill. SIMULATION RESULTS This section is devoted to compare the methods proposed above and to estimate how the performance of the methods is affected by the type of image. To carry out this analysis a set of random images were generated, which represent a small population of images. In others population of images, with different histogram patterns and charge of events, the results can vary in some methods, although the behaviour A, will be closer to the results here presented. Theses images was obtained considering two aspects: its The interest of this point is not to compare the execution histogram must be closer to Gaussian distribution and the time of each method, because the methods have to be number of events needed to transmit them, this is called implemented in hardware for a more real comparison. “image event charge” and this way. 100% event charge Therefore the interest yields in the behaviour of the corresponds to an image with all of pixel with inaximum execution time for each method respect to the image event value. In such a way, a image with 10% of event charge, charge. The test has been made by using the nine images represent an image that used 10% of the possible event. Fig. showed in Fig. 5. 5 shows the images used. Fig. 6 Software interface The execution 464 ( ptj) and the following event ( p$' ). The distance of the last event is calculated supposing that the next event is the first of a new sequence of the same image (we suppose that the image is continuously re-sent). i. Then we can measure the mean error for a pixel as the average of the differences between the ideal and real distance. The error expression is: gIQ., -d& e , = '.I k=I G.i It is easy to see that the worst case for this error measurement is which all the events are together in the address sequence (see Fig. 8). Therefore, in order to compare the error obtained for different methods and images, the error of each pixel must be normalized respect to the maximum error associated to the pixel. The following expression is the maximum error --. I ).(I--) with e.,j#l 4.j Scan Slice and Exhaustive method. For y,, = 1, the distribution error is zero, due to only one Fig. 7 shows the execution time versus the charge of event has to be sent. events in the image. Scan and Exhaustive methods follow an almost constant relation because the charge of events is traduced into an insignificant increasing in time execution, although this affect to the Exhaustive method in images with half charge of events. Random, Random Square and Scan Slice methods follow a growing up behaviour, due to the increasing number of events, with a less effect in the Scan Slice. Uniform method is also affected hv collisions (crows Fig. 8: The worst event distribution. _- up faster than others), hut it seems to be a relation between the number of collisions and the histogram, as can be seen comparing theses results with the typical image. Finally, we define a matrix with the same dimensions Of the image, where the @,j) element represents the error normalized for the pixel @,j): B. The distribution error In an ideal AER distribution all events for one pixel and image could be equidistant in time: constant frequency of events. In this section, the distribution of event obtained with each method is evaluated. The distribution error proposed measures how much the event distribution renerated by a method deviates from the ideal distribution. NE= - Let suppose Du is the ideal distance between events of the Fig. 9 shows the normalized distribution error calculated for the nine test images using the methods proposed. The xaxis represents the image event charge and the y-axis is the error. pixel 0,j) of a NxM image with K grey level values. N.WK D. .=- 4.j '.J where 4., is the intensity value of the pixel @,j). 465 Oi5tnbu18on error VE went charge + Scan-slice 8 Random 4 Random-Square B Exhaustive 06 02 01 Fig. I I: Typical image histogram to 20 30 40 y1 60 70 00 90 Image went charge (%) Fig. 9 Distribution error Method Mean Std. De~lstlon 69.75 17.14 99.22 49.19 35.58 99.22 84.95 14.69 98.43 17.25 Uniform Random (2bits) 34.92 As it can he seen, the minimum error is obtained with the The error decreases with the image event charge io all exhaustive method. methods except Random. In the scan methods the pixels with low intensity has a higher error of distribution inside the time period selected for transmi!ting the image, The Uniform method has the best results for the population of image selected, because there are very few In this paper six software methods for generating AER collisions. This method represent the closer solution to the streams from images stored in a computer's memoly have ideal distribution in the context presented. been presented. The different methods have been analysed Let us consider a typical case, Fig. IO shows a typical and tested by simulation software. It is necessary the grey level image and Fig. 11 its histogram. hardware implementation for real-time, and the A hardware platform that exploits these techniques is currently under development. For this goal. an analysis of different architectures for real time is being made. A dedicated hardware to write and read toifrom an AER bus is being developed using a standard FPGA-based prototyping board. It is still soon to conclude that the Uniform method is the most adequate method, as it can be expected. The hardware study will complement the work presented in this paper. 1V. CONCLUSIONS AND FUTURE WORKS . ... corresponding study. ., Fig. 10 Typical image Table I shows the maximum and mean normalized errors yields a significant improvement over the other methods. It can be Observed that the values for Uniform For more specific populations of images, the methods need to be analysed to clarify the most appropriate. There are several factors that can determine the selection of the method for the desired population: the necessity of real- '' percent. As it can be seen, the Uniform method proposed time, the distribution of events, whose have been analysed here. But if can be interesting to analyse the effect of the method sequence of events in traffic effect in the AER bus, where correspond to an image between the 80 and 90 of charge the density of in time could make the reSulfS of for the Gaussian histogram population showed in Fig. the methods. For example, in biomedical applications, the x- Between the methods that divide the time period in K ray or windows or slice, the Exhaustive method obtain the hest histogram. results. The Random-Square results are better than those obtained by the Random method. images have a non-gaussian 466 V. ACKNOWLEDGMENTS The authors wish to express their gratitude to the support given to this work by the European Commission through project CAVlAK ‘Convolution AEK Vision Architecture for Real-Time” (IST-2001-341024), funded by the European Commission, V Framework Programme “Information Society Technologies (IST) Programme”. VI. REFERENCES Ill A. Cohen, R. Douglas, C. Koch, T. Sejnowski, S. Shamma, T. Horiuchi, and G. lndiveri. Report to :he Nutional Science Fmmda:ion: Wurlrhop on Neurumorphic Engineering. Telluride, Colorado, USA, June-luly 2001. [w\*lv.ini.uni2h.chitellundc] [2] A. Linarcs-Barranco. “Esrudiu y evoluocid,~ de inte&ces pura lo conexi& de risiemm neuromdrfiios azedianie Addresr-Evmr- Repr~,~enturiort ”. Ph.D. Thesis, Univursiry of Seville, Spain, 2003 [3] Charles M. Higgins and Christof Koch. Udri-Chip Neuronwrphic Morion Processing. January 1999. [4] Kwabena A. Baahen. Commcmicu:ing Nne.onul Ennrembles beween Nruromorphic ChipA. Neurumorphic Systems. Kluwer Academic Pubiishen, Boston 1998. M. Siviloni, Wiring Considerorions in onnlvg VLSl Systems waiih .4pplicu!ion io Field-Progrummobie Neworh, Ph.D. Thesis, California Institute of Technology, Pasadena CA, I99 I [6] Misha Mahowaid. VLSl Analogs oJ Neuronol Vi~uol Processing: A Synthase o/Fo,ar and Function. Ph.D. Ihesis. California InslitUte of Technology Pasadena, Caiifomia 1992. Pierre L’Ecuyer, Fianqois Panneton. A hie!+ Cluss qfLineor Feedback Sh@ Register Generators. Proceedings of the 2000 Winter Simulation Conference. 181 Teresa Semno-Gotacredona, Andreas G. Andreou, Bemabe Linares- Barranco. AER hip Filrering Amhitectue fkr Viriorr-Processing Systems. IEEE Tmnsactions on Chuirs and Systems. Fundammtal Theory and Applications, Vol. 46, NO. 9. September 1999. [Y] Linear Feedback Shih Register V2.0. Xiiinx Inc. October 1, 2001. htm:llw~.xilinx.ca~i~~~~t~~. [SI [7] 467