Aproximación a la implementación de aplicaciones aero-espaciales en hardware

Aproximación a la Implementación de Aplicaciones Aero-espaciales en Hardware Víctor Diges Teijeira GRADO EN INGENIERÍA DE COMPUTADORES. FACULTAD DE INFORMÁTICA UNIVERSIDAD COMPLUTENSE DE MADRID CURSO 2014-2015 Trabajo Fin de Grado en Ingeniería de Computadores 29/06/2015 Directores: Marcos Sánchez-Elez Martin Inmaculada Pardines Lence Autorización de difusión Víctor Diges Teijeira 29/06/2015 El/la abajo firmante, matriculado/a en el Grado en Ingenría de Computadores de la Facultad de Informática, autoriza a la Universidad Complutense de Madrid (UCM) a difundir y utilizar con fines académicos, no comerciales y mencionando expresamente a su autor el presente Trabajo Fin de Grado: Aproximación a la Implementación de Aplicaciones Aero-espaciales en Hardware, realizado durante el curso académico 2014-2015 bajo la dirección de Marcos Sánchez-Elez Martín e Inmaculada Pardines Lence en el Departamento de Arquitectura de Computadores y Automática, y a la Biblioteca de la UCM a depositarlo en el Archivo Institucional E-Prints Complutense con el objeto de incrementar la difusión, uso e impacto del trabajo en Internet y garantizar su preservación y acceso a largo plazo. Resumen En la actualidad, los sistemas de hardware reconfigurable están muy extendidos en el entorno aeroespacial. Esto es debido a su gran potencia computacional comparada con la de soluciones software. En este proyecto se analizan las múltiples aplicaciones de las FPGAs en esta industria, y cómo la investigación espacial y de defensa han liderado el desarrollo de sistemas aeronáuticos electrónicos. Estos están presentes hoy en día en la mayoría de aeronaves comerciales. Además, se introducirán brevemente los efectos de la radiación del espacio en los elementos electrónicos, explicando cómo afectan a las memorias y los circuitos y cómo pueden ser detectados y corregidos por la FPGA. Se ha escogido el procesado de video en tiempo real como aplicación objetivo de este trabajo, mostrando las características de las FPGAs que pueden ser explotadas para obtener resultados con muy poca latencia. Se ha utilizado la herramienta Matlab para simular los algoritmos, indicando al mismo tiempo cómo podrían ser segmentados en una FPGA. Para mejorar los resultados se ha desarrollado un procedimiento para la detección de objetos para una vista de cámara móvil, basado en la eliminación de ruido de la imagen y en humbralado. Palabras clave FPGA, Aeroespacial, Visión por Computadora, Procesamiento de Video, Reconocimiento de Objetos. Abstract Nowadays, reconfigurable hardware systems are widely used in the airspace environment. This is thanks to their great computing power in comparison to software solutions. In this project we analyze the multiple applications of FPGAs in this industry, and also how the space and defense research have lead the development of electronic aeronautic systems. They are now present in most of the commercial aircrafts. In addition, we briefly introduce the effects of space radiation in electronic, explaining how they affect memories and circuits and how they can be detected and corrected by an FPGA. Real time video processing was chosen as a target application of this work, showing how FPGA’s characteristics can be exploited to obtain results with very low latency. Matlab tool was used to simulate the algorithms, providing insight on how they could be pipelined in an FPGA. In order to improve the results an object detection procedure for a moving camera view was developed, based on noise removal and thresholding. Keywords FPGA, Aerospace, Computer Vision, Video Processing, Object Recognition. Contents Index i 1 FPGA Applications in avionics 1 1.1 FlightControl............................ 2 1.2 Navigation and Monitoring . . . . . . . . . . . . . . . . . . . . . 3 1.3 AugmentedVision ......................... 4 1.3.1 Real Time analysis . . . . . . . . . . . . . . . . . . . . . 4 1.3.2 Intelligent Transport . . . . . . . . . . . . . . . . . . . . 5 1.3.3 Immersive Displays . . . . . . . . . . . . . . . . . . . . . 5 1.3.4 Image Stabilization . . . . . . . . . . . . . . . . . . . . . 6 1.4 Multispectral Image Processing . . . . . . . . . . . . . . . . . . 6 2 FPGA Applications in space 9 2.1 SingleEventEffects......................... 9 2.2 SEU detection and mitigation . . . . . . . . . . . . . . . . . . . 10 2.3 SEU Mitigation Approaches . . . . . . . . . . . . . . . . . . . . 11 2.3.1 On-chip detection . . . . . . . . . . . . . . . . . . . . . . 11 2.3.2 External detection . . . . . . . . . . . . . . . . . . . . . 11 2.3.3 Watchdogs.......................... 11 2.3.4 Dual and Triple Module Redundancy . . . . . . . . . . . 12 2.3.5 Lockstep Architecture . . . . . . . . . . . . . . . . . . . 12 3 Video Analysis: Tracking objects 13 3.1 Image Digitization . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.2 Pre-processing............................ 16 i 1.4. Multispectral Image Processing 6 many years, however enhanced vision systems have been certified for civil aviation less than 15 years ago. 1.3.4 Image Stabilization Cameras mounted in moving objects or vehicles receive part of this movement mainly as vibration. Even though physical solutions such as shock absorbers provide a good noise reduction, some video processing is needed to obtain a stable image. This is usually performed by FPGA and ASIC solutions. The processing unit needs to find the movement vector from the frames of the video stream and adjust each frame consequently[4][5]. Aircrafts can move freely on the 3 dimensional space, unlike land and sea vehicles. This adds another not desired movement in the output stream: the roll rotation. Gimbals are often used to provide aircraft cameras freedom of movement but usually only offer pan and tilt axis of freedom. Video stabilization can be obtained in two manners: obtaining the rotational vector from the frames or using the aircraft inertial navigation system (INS) to obtain the current rotation and adjust the image to it. 1.4 Multispectral Image Processing A multispectral image is one that captures image data at specific frequencies across the electromagnetic spectrum. It provides information not available by only exploiting the visible region of the electromagnetic spectrum[6]. Used mainly for topographic study, it’s become very important in defense and scientific observation. Non-visible spectrum imaging was first used during the Vietnam War, when color infrared imagery was used to distinguish artificial features, like camouflage, from vegetation. This technology led to the development of sensors to exploit a wider range in the electromagnetic spectrum which were later 1.4. Multispectral Image Processing 7 equipped in the Landsat satellites. Landsat program became the longest running enterprise for acquisition of satellite imagery of Earth and has launched eight satellites so far (Landsat 6 failed to reach orbit) and nowadays Landsat 7 and 8 are still active. Figure 1.2: Landsat8 Multispectral sensors produce a large set of images which have to be transmitted. Images need to be encoded and compressed in order to achieve good transfer rates, and for this purpose FPGAs prove to be useful thanks to their Single Instruction Multiple Data set (SIMD) computation capabilities[7]. Chapter 2 FPGA Applications in space Apart from high computational performance and other advantages already discussed, FPGA reconfigurability permits upgrades after launch that makes them highly suitable for space applications. Furthermore, this flexibility helps solving mishaps during runtime which can be more difficult to solve using ASICs or CPUs. 2.1 Single Event Effects Electronics main problem in space applications is the radiation. When a high-energy particle passes through the silicon substrate of a device, charged particles are created as the result of sub-atomic particle collisions. These particles are generated by an ionization trail along the path of the incoming particle and can interfere with the normal behavior of an electronic circuit[8]. The disruptions provoked by radiation are known as Single Event Effects. Depending of the severity, two kind of errors can be identified: Hard and Soft Errors. Soft errors are recoverable, but the system may need to be power-cycled or initiate a recovery procedure. Three types of soft errors can be identified[9]: Single-event transients (SETs) Occurs when a high-energy particle impacts a combinatorial path of a device and can induce a voltage/current 9 2.2. SEU detection and mitigation 10 spike. It can propagate to the rest of the circuit. Single-event upsets (SEUs) These are the result of high-energy particles causing a change in the state of a memory element (SRAM, flip-flop, or latch). These are the most common SEE in avionics applications. Single-event function interrupts (SEFIs) They are disruptions to normal device operation. These types of effects alter the functionality of the circuit and typically require reconfiguration/reset or power cycling for recovery. SEE can also cause very rare hard errors, which can be permanent. FPGAs are mainly susceptible to Single Event Burnout where the voltage/current spike produced by a high energy particle can provoke physical damage to the components of the circuit. 2.2 SEU detection and mitigation FPGAs use memory both in user logic (bulk memory and registers) and in Configuration Random Access Memory (CRAM) and these memories, along with flip-flops, can be upset by radiation. CRAM configures all logic and routing in the FPGA; if an SEU strikes a CRAM bit, the effect can be severe if it affects critical logic internal signal routing (such as a lookup table bit)[10]. Block RAMs can be protected with error-correcting code (ECC) and parity schemes. FPGA configuration memory, however, cannot be directly protected in the same manner as block memory via ECC or parity checks. SEU detection techniques that monitor device configuration memories are recommended. Some space-grade FPGAs include built-in configuration memory error detection, using ECC, but more recently, the use of flash memories has been proposed as an alternative, since they need a much higher charge to discharge the floating gate and switch state. 2.3. SEU Mitigation Approaches 11 2.3 SEU Mitigation Approaches Manufacturers develop radiation hardened space-grade FPGAs to counter measure SEUs adding physical protection. In addition, other design measures can be taken: 2.3.1 On-chip detection FPGA manufacturers offer IP cores to mitigate SEUs, monitoring and repairing FPGAs configuration memory. On-chip processing is autonomous: the FPGA device determines whether it is affected by an SEU, without needing external logic. These cores have the ability to detect the sensitivity of the failure and assert an error signal so the system can provide an appropriate response according to its severity. 2.3.2 External detection SEU processing IP cores can be configured to use an external processor. An external CPU receives an interrupt request signal when the FPGA detects a SEU. The CPU then reads the Error Message Register and performs the sensitivity lookup. This system frees up FPGA memory space and configurable logic. 2.3.3 Watchdogs Watchdogs are special-purpose hardware modules attached to the processor. They have limited impact on the performance of the system but they may require special development efforts at the software level in its management. These timers monitor the control-flow execution, the data accesses patterns and perform consistency checks, while letting the software running on the processor mostly untouched. 2.3. SEU Mitigation Approaches 12 2.3.4 Dual and Triple Module Redundancy These solutions are very useful when system downtime is critical. In Triple Module Redundancy (TMR) three identical instances of the hardware are run and their outputs are processed by a voting system to produce a single output. If any of the three instances fails due to an SEU, the other two can correct and mask the error. This approach implies a penalty in both area and power consumption, but it is by far the best available alternative to protect the programable logic against SEU. Since in Dual Module Redundancy a discrepancy is not easily solved by voting, these systems usually work in a master-slave configuration. The slave works as a hot-standby to the master. In case the master fails, the slave is ready to continue execution as a backup. 2.3.5 Lockstep Architecture In a Lockstep Architecture, two systems are synchronized to start from the same state and both receive the same inputs. Therefore the state of both systems should be equal at every clock cycle unless an abnormal condition occurs[11]. Consistency checks are performed periodically, either by time or when the execution reaches a milestone. When the states differ due to an error, the execution must be halted and restarted. Since a restart from the beginning is highly expensive, checkpoints are used to keep a copy of an error-free state in safe storage. Whenever a consistency check shows that the response of the two systems are the same, their context1is saved as a checkpoint in error-protected memory. If the consistency check fails, a rollback operation must be performed, restoring the previous context of a checkpoint and the execution is resumed. 1All information needed to restore the system to a valid state Chapter 3 Video Analysis: Tracking objects Among all the FPGA applications for modern civil and military aviation, as well as for space equipment, artificial vision was chosen to expand on in this project. It benefits enormously from FPGA features like parallelism and high computing power to provide real time video analysis. In this project, we will focus on an application to identify objects in a video taken from a moving camera. The video had to be downscaled and trimmed due to computer performance restrains. Modern serial processors are able to perform some of the processing required for this application with low latency, but they are not very efficient and have trouble keeping an affordable latency when introducing high quality video like current standard 1080p1at 60 frames per second. With current tendency to increase vertical resolution up to 4K pixels, serial processors are not a good solution for video processing and analysis. FPGAs on the other hand can be programmed to perform parallel, pixel-wise operations over a frame buffer which latency is of barely a few clock cycles, allowing also pipelining. Artificial vision is composed of many stages: •Image Digitalization 11920 pixels in width and 1080 pixels in height frames, with progressive scan 13 3.1. Image Digitization 14 •Pre-processing •Segmentation •Representation •Feature extraction •Classification and identification In this project, the pre-processing stage will be explained in depth, along with some algorithms used in it, since it is the phase that most benefit from FPGAs capabilities. Other stages will be analyzed as well in a more theoretical approach. 3.1 Image Digitization An image is an optical representation of one or many objects illuminated by one or more sources of radiation (visible light, x-ray, ultrasonic, infra-red, etc.). Part of this radiation is absorbed by the object and the rest is reflected, depending of the physical-chemical characteristics of the object. There is no image capturing system as precise as the human (or animal) visual system. From an image in the real world, the first step in digitizing is an optical system, usually formed by a set of lenses, which acts as a low-pass filter removing high frequencies (details). Next step is capturing the image itself using a sensor. Common sensors nowadays use CMOS (Complementary Metal-Oxide-Semiconductor) and CCD (Charge-Coupled Devices) technology. They are composed by an array of photo-sensitive elements which transform light intensity to an electric signal. The quantity of these elements per surface unit defines the resolution of the images. 3.1. Image Digitization 15 Figure 3.1: Bayer Pattern The photo-sensitive elements can only perceive the intensity of the light, which would generate a grayscale picture. In order to separate colors, a filter must be applied before the sensor so that it only reads the intensity of that color in particular. The most used approach nowadays is a Bayer filter mosaic. It is a color filter array for arranging red, green and blue color filters on a square grid of photosensors. A last layer of hardware is needed to convert these analog signals to a digital value. This analog to digital converter performs quantization of the input, hence introducing some error in the conversion. The resolution of the converter indicates the number of discrete values it can produce over the range of analog values which in this case represents the intensity of the color. As a result of this conversion, an N×Mmatrix of integer or real numbers is obtained. Each element of this matrix is called a pixel. If the image is color separated it becomes a 3-dimensional array, with one layer for each color (usually three). It’s easy to calculate the required space to store an image from here. The general formula is: Sizebytes =Width ×Height ×ColorDeepness ×NColors/8 For a raw 1080p image with 10 bit color deepness the size is 1290 ×1080 × 10 ×3/8 = 7776000 bytes or 7.77 Mb. At a rate of 60 frames per second, each second 466.56 Mb of data are generated. Huge bandwidth is needed in order to transport such amount of data, hence compression and encoding are usually performed. Software solutions are widespread to general public but encoding performance in a serial processor is rather inefficient. On the other hand, commercial IP cores for FPGAs and ASICs2have a very good performance, with 2Application-Specific Integrated Circuit 3.2. Pre-processing 22 Figure 3.7: Frame from figure 3.6 after histogram equalization 5. Rescan the image and write an output image with gray levels gq, writing: gq=T[gp] The result of histogram equalization over the frame from figure 3.6 can be seen in the figure 3.7. The gray levels have been spread along the dynamic range. Being a discrete environment, this is the best result obtainable. The Matlab code can be consulted in the listing 2. Histogram equalization is a global operation that requires reading the whole image and store it in a frame buffer to operate over it. This breaks the pipeline and adds a latency of 1 frame per second to the process. 3.2.4 Noise reduction Usually, images have white noise, with zero mean and finite variance. Noise reduction helps improving the results of the later image processing, such as border recognition. The approach to remove this noise is by low-pass filters[14]. The most used are: Median filter Although the same windowing process is used as in a convolution, median filter doesn’t perform any sum of the neighbor pixels. In stead, the median is the number separating the higher half of the neighbor elements from the lower 3.3. Segmentation 23 half. The median filter is a nonlinear digital filtering technique. It needs a lot of computational effort since the median of the window of each element of the image has to be calculated. For small to moderate levels of noise, the median filter is demonstrably better than other filters at reducing noise and preserving borders. Mean filter 1/9 1/9 1/9 1/9 1/9 1/9 1/9 1/9 1/9 Figure 3.8: Mean filter kernel This filter computes the average of all the pixels of a window centered on the output pixel. It is easily implemented as a convolution using kernels such as in figure 3.8. However, this filter is very aggressive with the borders despite its gain in performance. Both median and mean kernels don’t need to be square, although they are the most used. The size is usually 3×3,5×5, etc. But it’s been demonstrated that if the size is very big, that is 7×7or 9×9, the results are not good. In stead, if the image is very noisy, it’s better to apply smaller kernels in cascade, that is, apply the same filter to the result of a previous application. Gaussian blur This filter uses a Gaussian function, with a bell shape, that is less aggressive to the borders, since the center of the kernel will attenuate more the noise than the peripheral elements. However, the use of exponentials, and complex divisions in the gaussian function, makes it unsuitable for testing with simple FPGAs. 3.3 Segmentation The goal of image segmentation is to separate the interesting objects from the rest, considered as background. Segmentation is usually considered as a process of classifying objects in an image. The level of segmentation depends 3.3. Segmentation 24 on the application. In this case, we are analyzing videos taken from a moving camera (another plane) and hence background identification and subtraction is not an easy task. In stead, the frames must be carefully segmented and thresholded. An advantage of using FPGAs operating in real time is that the algorithms can be readjusted with feedback so thresholds and depth of segmentation can be adapted. 3.3.1 Border Detection A border can be defined as a significant change in the intensity of the pixels of a region of an image, or as a high gradient on a point. Border detection consists of identify which pixels can be considered part of a border. The knowledge of this points allows the construction of the borders and hence the bounding of the frontiers of the regions on an image. Border detection can yield information about the direction of the border, it’s intensity (the difference in contrast) or it’s direction (which part is brighter than the other). In addition, as image formation is not a perfect process, border detection has to deal with noise or fragmentation (some parts of the contour are lost). In order to help the detector, a noise reduction process should be applied previously. A median filter will be applied before the border detection algorithm for the examples shown in the next sections. Sobel Operator It is one of the classic techniques in border detection based in computing a discrete approximation of the gradient of the grayscale image. It creates an image that emphasizes edges and transitions. At each pixel, the value of the output is an approximation of the norm of the gradient vector of the input pixel. The Sobel operator is based on convolving the image with a 3.3. Segmentation 25 -1 0 1 -2 0 2 -1 0 1 -1 -2 -1 0 0 0 1 2 1 Figure 3.9: Vertical and horizontal kernels for the Sobel operator Figure 3.10: Left, border detection with Sobel operator over the frame from figure 3.6; right with median filter applied before border detection. small and integer valued filter in horizontal and vertical direction which can be implemented in an FPGA with the design from the figure 3.3. There are two kernels for the Sobel operator, one for vertical borders and other for horizontal as shown in figure 3.9. Additionally, other filters can be created to identify diagonal lines by rotating these filters. Both filters must be applied to the original image, generating two frames, so the real output must be the mean of the two. Ideally, the root mean square should be used, but in in an FPGA environment is easier to calculate the mean of two values in stead of calculate a square root. Laplacian operator Another classic approach for border recognition is by using the second derivative. The Laplacian operator is widely used to accentuate a border without taking into account its direction. The discrete version of this filter can be seen in figure 3.11. However, the second derivative is very sensitive to noise, and so usually it is used together with a Gaussian low-pass filter. Since the convolution operation is associative, the Laplacian and Gaussian filters can be convolved beforehand and then convolve this hybrid filter with the image to 3.3. Segmentation 26 0 1 0 1 -4 1 0 1 0 0.5 1 0.5 1 -6 1 0.5 1 0.5 Figure 3.11: Two versions of Laplacian filters. The one in the right includes diagonal lines Figure 3.12: Laplacian operator over the frame from figure 3.6 obtain the borders. During the tests performed with Matlab the Laplacian operator showed good results identifying corners (figure 3.12), but not so good in the integrity of the border where Sobel had better results. Hence the chosen operator was Sobel with a previous (double) median filter smoothing. Its Matlab code can be consulted at listing 3. 3.3.2 Object Recognition An advantage of using Sobel operators to detect borders is that they return the intensity of the border, allowing thresholding to discard low-gradient transitions that can be noise or background while enhancing objects. The thresholding operation can be easily implemented in a pipeline since it is a punctual operation. A threshold Tis the value applied to a transformation of input 3.4. Feature Extraction 27 frame f(x, y)into output g(x, y)as in the formula: g(x, y) =    1if f(x, y)≥T 0if f(x, y)< T FPGAs allow this threshold to be dynamically calculated and adjusted in real time so it meets the requirements of the application. Matlab simulation can be found in listing 4. The frame is now a cloud of border points. A high density of these points in a given area can be assumed as a separated object, hence applying a mean filter with a big enough window can yield the density of border points in the area surrounding each pixel as a fraction. Applying a threshold to the resulting frame with the percentage value that could be considered an object. An special Matlab function (listing 5) was created to perform these two operations and yield a binary image that suits the next steps. 3.4 Feature Extraction 3.4.1 Connected-component labeling Figure 3.13: Already processed neighbors (8connection) Connected-component labeling is an algorithm that labels subsets of connected components based on a given heuristic in a binary image. This serves to identify and separate the clouds of borders generated in the previous step. The classic algorithm is performed in two passes. The algorithm examines the already processed neighbors of each pixel shown in figure 3.13 and determines which label to assign according to the procedure defined by Milan Sonka[13] as follows: 1. First pass: Search the entire image Rby rows and assign a non-zero 3.4. Feature Extraction 28 value vto each non-zero pixel R(i, j). The value vis chosen according to the labels of the pixel’s neighbors. •If all the neighbors are background pixels (with pixel value zero), R(i, j)is assigned a new (and as yet) unused label. •If there is just one neighboring pixel with a non-zero label, assign this label to the pixel R(i, j). •If there is more than one non-zero pixel among the neighbors, assign the label of any one to the labeled pixel. If the labels of any of the neighbors differ (label collision), store the label pair as being equivalent. Equivalence pairs are stored in a separate data structure— an equivalence table. 2. Second pass: All of the region pixels were labeled during the first pass, but some regions have pixels with different labels (due to label collisions). The whole image is scanned again, and pixels are re-Iabeled using the equivalence table information (for example, with the lowest value in an equivalence class). Label collisions are pretty common. They are produced when the blob has an Ushape. In the first pass the algorithm will detect each top part of the U as different labels and when it reaches the bottom there are 2 different labels in the neighbors. This conflicts are solved during the second pass. Hence, this algorithm is highly inefficient since it needs to perform two passes over each frame to correctly detect all objects and needs to use an intermediate frame buffer. Some investigators have proposed implementations for this algorithm in real-time using FPGAs, exploiting their capabilities in parallelization and pipelining. Donald G. Bailey and Christopher T. Johnston first approach [15] avoided the need for buffering the image between passes by performing just one pass but had problems with worst case scenarios where the number of labels generated prior to merge was huge. In the next iteration[16], this problem was solved by reusing the labels. One last approach implemented the 3.5. Representation 29 Figure 3.14: Object recognition plotted over original video gathering of feature data for each region in parallel with labeling, enabling a single streamed pipeline implementation[17]. This algorithm relies on lookup tables for merging, and so adapting the algorithm to Matlab code is not an easy task. However, Matlab offers a function that labels the regions of a binary image, and was used in listing 6. 3.5 Representation Once the frames have all their important objects labelled, a good way to display this data is by plotting it over the original video, since the processed one no longer holds the visual features of the original. The labeled pixels of each frame have to be search to separate their regions and obtain their information such as maximum and minimum on both axis and/or their centroid. This data is later used to generate rectangles that will show the identified objects of the frame. While the information gathering can be performed in the pipeline, the graphics generation can’t. Taking into account the fact that they are applied over the original frame, the plotting doesn’t need to wait for the frame to be 3.6. Final result 30 Figure 3.15: Sequence of steps completely out of the pipeline. In the Matlab function in listing 7, the Visual library is used to generate the graphics, for simplification sake. The final result can be seen in figure 3.14. The process is able to recognize objects, but it needs readjustment in real time to capture most of the important data. 3.6 Final result The sequence of steps in Matlab can be found in Listing 8. Executing the procedure on a computer takes a couple of minutes while the delay on an FPGA should be of about 1-2 frames. Hence, the latency in serial computers increases linearly with the length of the video, making the process unaffordable in a stream, while the pipelined algorithm on an FPGA has a fixed latency. 3.6. Final result 31 Figure 3.16: Alternative for Histogram Equalization Parallel calibration can be introduced in the thresholding and object location steps when implementing the algorithm in the FPGA as can be seen in figure 3.15. The major delay is produced in the histogram equalization step because it needs a frame buffer to operate, hence stalling the pipeline. However, the detection step can be parallelized, reading all input pixels in the stream and calculating the lookup table. The grey value correction can then be executed with a latency of one frame, delaying only this step in stead of the whole pipeline. Luminosity doesn’t change suddenly in open areas so the delay is affordable. The output video generated in this work can be seen in https://youtu. be/nqsTOEPAwyo Bibliography 38 [13] Milan Sonka. Image Processing, Analysis, and Machine Vision. 2008. [14] Roberto Rodriguez Morales and Juan Humberto Sossa Azuela. Procesamiento y Análisis Digital de Imágenes. 2011. [15] Donald G. Bailey and Christopher T. Johnston. “Single Pass Connected Components Analysis”. In: Proceedings of Image and Vision Computing (2007). [16] Ni Ma, Donald G. Bailey and Christopher T. Johnston. “Optimised Single Pass Connected Components Analysis”. In: ICECE Technology, 2008. FPT 2008. International Conference on (2008). [17] Donald G. Bailey, Christopher T. Johnston and Ni Ma. “Connected components analysis of streamed images”. In: Field Programmable Logic and Applications, 2008. FPL 2008. International Conference on (2008). Appendix: Source Code Listing 1: Grayscale Conversion 1function [ vidgray ] = vid2grayscale ( vid ) 2vidgray = uint8 ( zeros(size ( vid ,1) , size( vid ,2) , size ( vid ,4) ) ) ; 3for i =1: s i z e ( vid , 4) 4vidgray ( : , : , i ) = vid ( : , : , 1 , i ) ∗0.25 + vid ( : , : , 2 , i )∗0.5 + vid ( : , : , 3 , i ) ∗0.125; 5end; 6vidgray=squeeze ( vidgray ) ; 7end Listing 2: Histogram Equalization 1function [ videq ] = histEqvid ( vid ) 2videq=uint8 ( zeros(s i z e ( vid ) ) ) ; 3 4[M, N, T] = size ( vid ) ; 5G = 256; 6for t=1:T 7%Scan every pixel and increment the relevant member of H−− i f pixel p has 8%intensity gp , perform 9H = uint32 ( zeros(1 , G) ) ; 10 for i = 1:M 11 for j = 1:N 39 Bibliography 40 12 gp = vid ( i , j , t ) ; 13 Temp = H(gp+1)+1; % Adjust gp to go from 1 to G, not 0 to G−1 14 H(gp+1) = Temp; 15 end 16 end 17 18 %Form the cumulative image histogram Hc and create the lookup table for step 4: 19 Hc = uint32 ( zeros(1 ,G) ) ; 20 T = uint32(zeros(1 ,G) ) ; 21 Hc(1) = H(1) ; 22 T(1) = round (((G−1)/(N∗M) ) .∗H(1) ) ; 23 for p = 2:G 24 A = Hc(p −1) + H(p) ; 25 Hc(p) = A; 26 B = round (((G−1)/(N∗M) ) .∗Hc(p) ) ; 27 T(p) = B; 28 end 29 30 %Rescan the image and write an output image with gray−l e v e l s gq 31 for i = 1:M 32 for j = 1:N 33 gp = vid ( i , j , t ) ; 34 Temp = T(gp+1) ; % Adjust gp to go from 1 to G, not 0 to G−1 35 videq ( i , j , t ) = Temp; 36 end 37 end 38 end 39 end Bibliography 41 Listing 3: Border detection with Sobel operator, smoothed with double median filter 1function [ bVid ] = vidBorders ( vid ) 2%Creation of the two Sobel f i l t e r s 3hSobel= [−1−2−1; 0 0 0; 1 2 1 ] ; 4vSobel= [−1 0 1; −2 0 2; −1 0 1 ] ; 5 6%Memory allocation for the buffers 7bVidBuff = zeros(size( vid ( : , : , 1 ) ) ) ; 8bVidH = zeros(s i z e ( bVidBuff ) ) ; 9bVidV = zeros(s i z e ( bVidBuff ) ) ; 10 11 for i =1: s i z e ( vid , 3) 12 %Double application of the median f i l t e r to smooth the frame 13 bVidBuff ( : , : , i ) = uint8 ( medfilt2 ( vid ( : , : , i ) ) ) ; 14 bVidBuff ( : , : , i ) = uint8 ( medfilt2 ( bVidBuff ( : , : , i ) ) ) ; 15 %Convoluting of both kernels with the input frame. 16 %Matlab requires conv2 parameters to be of type single. 17 %The ’same ’ parameter esta b lishe s that the output frame i s the same s i z e as the input 18 bVidV ( : , : , i ) = uint8 ( conv2( s ingle ( bVidBuff ( : , : , i ) ) , vSobel , ’same ’ ) ) ; 19 bVidH ( : , : , i ) = uint8 ( conv2( s ingle ( bVidBuff ( : , : , i ) ) , hSobel , ’same ’ ) ) ; 20 end; 21 bVid=uint8 (( bVidH+bVidV) ./2) ; 22 end Bibliography 42 Listing 4: Thresholding 1function [ vidThres ] = vidThreshold ( vid , threshold ) 2%Memory allocation for the r esul ting frame 3vidThres = l o g i c a l ( zeros(s i z e ( vid ) ) ) ; 4 5for i = 1: size( vid ,3) 6vidThres ( : , : , i )=(im2bw( vid ( : , : , i ) , threshold ) ) ; 7end; 8%Return matrix i s converted to uint8 to serve as input for next steps 9vidThres = uint8 ( vidThres .∗255); 10 end Listing 5: Object detection 1function [ vidO ] = locateObjects ( vidI , threshold ) 2 3mean = (1/121)∗( ones (11 ,11) ) ; 4vidBuff = uint8(zeros(size( vidI ) ) ) ; 5vidO = l o g i c a l ( zeros(s i z e ( vidBuff ) ) ) ; 6 7for i =1: s i z e ( vidI ,3) 8vidBuff ( : , : , i ) = uint8 ( conv2( s i ngle ( vidI ( : , : , i ) ) ,mean ,’same ’ ) ) ; 9vidO ( : , : , i )=(im2bw( vidBuff ( : , : , i ) , threshold ) ) ; 10 end 11 end Listing 6: Connected-Component Labeling 1function [ vidO , nObjects ] = cclVid ( vidI ) 2nObjects = uint8 ( zeros(1 , size ( vidI ,3) ) ) ; 3vidO = uint8 ( zeros(s i z e ( vidI ) ) ) ; 4for i =1: s i z e ( vidI ,3) 5%The Connected Component Labeling algorithm i s Bibliography 43 very u n e f f i c i e n t to implement in Matlab due to the fa ct that Matlab i s not prepared to work with complex data st ructur es l i k e lookup tables , stacks , etc . 6%However , Matlab o f f e r s a function that performs labelin g on binary images 7[ vidO ( : , : , i ) , nObjects ( i ) ] = bwlabel ( vidI ( : , : , i ) ) ; 8end 9end Listing 7: Objects representation on video 1function [ vidO ] = plotVideo ( vidRGB , vidLabeled , nObjects ) 2%In order to plot f i g u res in Matlab , an shapeInserter object , included in the vision library , i s needed 3shapeInserter = vision . ShapeInserter ( ’LineWidth ’ ,2 , ’ BorderColor ’ ,’Custom ’ ,’CustomBorderColor ’ , [255 0 0]) ; 4vidO=uint8 ( zeros(size (vidRGB) ) ) ; 5 6for t=1: s i z e ( vidLabeled ,3) 7%I n i t i a l i z e the output with the original , color video 8vidO ( : , : , : , t ) = vidRGB ( : , : , : , t ) ; 9[ y , x]=ndgrid (1: s i z e ( vidLabeled ,1) ,1: size ( vidLabeled ,2)); 10 %Itera te over the detected " blobs " of each frame 11 for k=1: nObjects ( t ) 12 %calculate the max and min dimensions to plot rectangles 13 maxx=max(y( vidLabeled ( : , : , t )==k) ) ; Bibliography 44 14 minx=min(y( vidLabeled ( : , : , t )==k) ) ; 15 maxy=max(x( vidLabeled ( : , : , t )==k) ) ; 16 miny=min(x( vidLabeled ( : , : , t )==k) ) ; 17 %Define the i n i t i a l points and dimension of the rectangle 18 rectangle = int32 ( [ miny , minx , maxy−miny , maxx−minx ] ) ; 19 %Draw the rectangle 20 vidO ( : , : , : , t ) = step ( shapeInserter , vidO ( : , : , : , t ) , rectangle ) ; 21 end 22 end 23 end Listing 8: Sequence of stages of video processing 1load(’mov ’ ) ; 2gray = vid2grayscale (mov) ; 3eq = histEqvid(gray ) ; 4borders = vidBorders ( eq ) ; 5bordersThres = vidThreshold ( borders , 0.35) ; 6obj = locateObjects ( bordersThres , 0.15) ; 7[ labeled , nObjects ] = cclVid ( obj ) ; 8output = plotVideo (mov, labeled , nObjects ) ; 9implay ( output ) ;