M Pérez-Patricio

Abiel Aguilar-González

M Arias-Estrada

H R Hernández-De León

J L Camas-Anzueto

J A De Jesús Osuna-Coutiño

J A De

J Osuna-Coutiño

An FPGA stereo matching unit based on fuzzy logic

Keywords: Stereo matching, Fuzzy logic, FPGA

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Depht values of the points contained in an image is one of the most used tasks of the computer vision systems and has been used in several applications such as positioning systems for mobile robots and both recognition, detection and threedimensional reconstruction of objects [START_REF] Parrilla | Fuzzy control for obstacle detection in stereo video sequences[END_REF][START_REF] Rong | Recognition of clustered tomatoes based on binocular stereo vision[END_REF][START_REF] Correal | Automatic expert system for 3d terrain reconstruction based on stereo vision and histagoram matching[END_REF][START_REF] Delmerico | Building facade detection, segmentation, and parameter estimation for mobile robot stereo vision[END_REF][START_REF] Åuligoj | Object tracking with a multiagent robot system and a stereo vision camera[END_REF][START_REF] Yang | Human detection for a robot tractor using omni-directional stereo vision[END_REF][START_REF] Roberto Marzotto | A real-time versatile roadway path extraction and tracking on an fpga platform[END_REF]. In stereo vision technique the correspondence between stereo pairs and the geometrical configuration of the stereo camera allows to obtain images of depth called disparity maps. In order to determine a disparity map it is necessary to measure the similarity of the points contained in the stereo pair. Techniques to determine these similarities are divided in two categories: area-based algorithms [START_REF] Stefano | A fast area-based stereo matching algorithm[END_REF][START_REF] Aguilar-Gonzalez | An fpga correlation-edge distance approach for disparity map[END_REF] and feature-based algorithms [START_REF] Feiyangcheng | Stereo matching by usingthe global edge constraint[END_REF][START_REF] Jung | Stereo reconstruction using high-order likelihoods[END_REF].

Area-based algorithm use the color value of the surrounding pixels to the interest pixel and produce dense disparity maps, i. e., these compute the disparity value for each pixel in the input stereo pair. The main characteristic of area-based algorithms is mathematical simplicity and low runtime. On the other hand, feature-based algorithms are based on specific interest points and are more stable against changes of contrast, enviroment conditions and illumination due to these represent the geometric properties of the input stereo pair. However, these algorithms possess high runtime and high mathematical complexity.

Related works

FPGA devices allow the implementation of dedicated computational architectures that can accelerate algorithms. In previous work there has been several FPGA stereo matching architectures reported in the literature [START_REF] Isakova | Fpga design and implementation of a real-time stereo vision system[END_REF][START_REF] Jin | Fpga design and implementation of a real-time stereo vision system[END_REF]. However, in most of these FPGA architectures the authors have been concentrated in the accuracy level and not in the performance regarding to hardware resource consumption, which is an important parameter in mobile autonomous applications in which the use of small FPGA devices and small power sources are required.

FPGA implementations

The system presented in [START_REF] Woodfill | Real time stereo vision on the parts reconfigurable computer[END_REF] consists in a 4×4 array of FP-GAs connected in mesh type configuration, authors use a maximum total of near 35,000 LUT of 4 inputs, allowing to process 40 frames per second for images of 320×240 pixel resolution. In [START_REF] Darabiha | Reconfigurable hardware implementation of a phase-correlation stereo algorithm[END_REF], a structure based on four FPGAs Virtex 2000E of Xilinx is presented, obtaining dense disparity maps at a speed of 40 frames per second for images of 256×360 pixel resolution. In [START_REF] Diaz | Fpga based realtime opticalflow system[END_REF], the use of a single FPGA is proposed, the developed system processes images at 30 frames per second using images of 640×480 pixel resolution. The architecture developed in [START_REF] Niitsuma | High-speed computation of the optical flow[END_REF], uses a technique based on SAD to calculate the optical flow efficiently, the system generates dense disparity maps at speeds superiors to 800 frames per second for images of 320×240 pixels using a correlation window of 7×7 and a maximum expected disparity equal to 121.

A modification of SAD is shown in [START_REF] Lee | Real-time stereo vision on a reconfigurable system[END_REF], the authors of this work synthesize diverse versions of SAD to determine the needs and the performance of the hardaware resources, by decomposing the correlation window of SAD in rows and columns using buffers a saving of resource of around 50% is reached. Using different forms of windows, the high consumptions of memory decreases without any detriment of the quality. Disparity maps are calculated at speed of 122 frames per second for images of 320×240 pixels and a maximum expected disparity equal to 64.

The architecture in [START_REF] Masrani | A real-time large disparity range stereosystem using fpgas[END_REF] uses four FPGAs to conduct a rectification in real-time, later, a verification of left-right consistency was applied in order to improve the quality of the produced disparity map. Speeds of 30 frames per second are reached for images of 640×480 pixel resolution and a maximum expected disparity equal to 128. In [START_REF] Aguilar-Gonzalez | An fpga correlation-edge distance approach for disparity map[END_REF] an FPGA correlation-edge distance approach is proposed. Speeds of 76 frames per second are reached for images of 1280×1024 pixel resolution and a maximum expected disparity equal to 15. By using a geometric feature, the euclidean distance between the selected point and the nearest left edge, the developed FPGA architecture provides a improvement over others conventional correlation-based stereo matching algorithms.

Fuzzy logic approaches

In [START_REF] Kumar | Stereo matching algorithms based on fuzzy approach[END_REF], similarity measure for stereo matching based on fuzzy relations is proposed. The strength of relationship of fuzzy data of two windows in the left image and the right image is determined by applying fuzzy aggregation operators. However, these measures fail to establish correspondence of the occluded pixels. In order to outperform the performance in the occluded pixels an modification of the weighted normalized cross correlation (WNCC) algorithm based on fuzzy relations of fuzzy data is used for the stereo matching process.

Authors of [START_REF] Ghazouani | Fuzzy sets based improvement of a stereo matching algorithm with balanced correlation window and occlusion detection[END_REF] present an modification of the Zitnick and Kanade stereo matching algorithm [START_REF] Zitnick | A cooperative algorithm for stereo matching and occlusion detection[END_REF]. The authors propose the use of a balanced correlation window. In addition, the use of a new fuzzy factor in the calculation of initial matching values which expresses the possibility of matching between two pixels and a new iterative function for the refinement of the initial matching values are presented. Experimental results are evaluated on synthetic and real images and a comparison of the results regarding to other algorithms reported in the literature, using the ground truth data supplied by the University of Tsukuba, is presented. Finally, in [START_REF] Georgoulas | A real-time fuzzy hardware structure for disparity map computation[END_REF] an FPGA module suitable for real-time disparity map computation is presented. This enables a hardwarebased fuzzy inference system parallel-pipelined design, for the overall module, implemented on a single FPGA device with a operating frequency of 138 MHz. This provides disparity map computation at a rate of nearly 440 frames per second, for a input stereo pair with a disparity range of 80 pixels and 640×480 pixel resolution. The proposed method allows high speed processing, enabling a suitable module for real-time stereo vision applications.

The proposed method

Stereo matching algorithms suitable for real-time processing have been studied by several authors, section 2.1. However, most of these algorithms possess high mathematical complexity; therefore, large FPGA devices are required in order implement them. On the other hand, although some approaches based on fuzzy logic have been reported in the literature section 2.2, the algorithms described in [START_REF] Kumar | Stereo matching algorithms based on fuzzy approach[END_REF][START_REF] Zitnick | A cooperative algorithm for stereo matching and occlusion detection[END_REF] presented high mathematical complexity and do not allow to be implemented in dedicated hardware for real-time processing such as FPGA devices. In case of the FPGA architecture in [START_REF] Georgoulas | A real-time fuzzy hardware structure for disparity map computation[END_REF] possesses high accuracy and high speed processing. However, the developed module maintains high hardware resource consumption.

The main objective in this research is to develop an FPGA stereo matching unit suitable for real-time processing. The disparity maps are computed at a rate of 76 frames per second for input stereo pairs of 1280×1024 pixel resolution and a maximum expected disparity (d max ) equal to 15. In order to reach high accuracy level the use of multiple similarity parameters and a fuzzy approach is proposed. Furthermore, to obtain high speed processing, the proposed method was implemented in an FPGA device. On the other hand, in order to maintain low hardware resources consumption it is proposed the use of new strategies such as: a fuzzy inference system based on point-slope equations and the use of storage vectors. Finally, to obtain an appropriate configuration regarding to the environment setting of the input stereo pair, the developed FPGA architecture allows to set up the exposition of the cameras and allows scalability for different levels of maximum disparity of simple and systematic form. This allows that the resulting hardware can be applied to a wide range of applications of real-time stereo vision.

A general block diagram of the proposed method is shown in the Figure 1, the data obtained through a stereo camera is processed to the cadence of video and it is simultaneously computed three similarity parameters inherent to each pixel. 1correlation obtained via the Sum of absolute differences (SAD) algorithm [START_REF] Olivares | Minimum sum of absolute differences implementation in a single fpga device[END_REF][START_REF] Hoa | Efficient determination of disparity map from stereo images with modified sum of absolute differences (sad) algorithm[END_REF][START_REF] Wong | Sad implementation in fpga hardware[END_REF][START_REF] Colodro-Conde | Evaluation of stereo correspondence algorithms and their implementation on fpga[END_REF]. 2 -similarity of the distance in pixels to the closer left edge. 3 -similarity of the distance in pixels the closer right edge. Later, these three parameters are submited to a fuzzy inference system which assigns fuzzy-similarity values for the zero up to d max disparity levels. Finally, the value of disparity is assigned as the index that maximizes the fuzzy-similarity value.

Correlation computation

In majority of area-based algorithms, a rectangular vicinity centered on a reference pixel in one of the images from a stereo pair is compared with similar vicinities for some pixels in the same raster line of the other image. Vicinities are called correlation windows and can be compared using a correlation-based measure such as SAD, equation 1; where 2w + 1 is the size of the correlation window centered in the pixel located in the (x, y) position. I l , I r are the grayscale values of the pixels in the images left and right respectively and z takes values from 0 up to d max .

Crl(x, y, z) = u=w,v=w u=-w,v=-w

|I l (x + u, y + u) -I r (x + u + z, y + u)| (1)

Similarity of the edge distances

The euclidean distance between each pixel with coordenates I l (x, y 1 ) or I r (x, y 1 ) and the closer left edge (d 1 ), considering images of X × Y resolution and a maximum level of expected disparity equal to d max is computed via equations 2 -3; where β represents the value of threshold to determine an edge. δ is defined as l or r for the left or right images, respectively. z ranges from 0 up to d max . y 1 ranges from 1 up to Yd max and g 1 is defined by equation 4.

d 1 (x, y 1 , z) = l = 0, k 1 (x, y 1 , z) < β l = l + 1, k 1 (x, y 1 , z) > β (2)
k 1 (x, y 1 , z) = |I δ (x, y 1 + z) -I δ (x, y 1 -g 1 + z)| (3)
g 1 = 1, y > 1 0, otherwise (4)
In Figure 2 the left image of the Venus scene is shown. On the other hand, Figure 3 shown the distance to the closer left edge for all the pixels that integrate the scene. The darker values represent small distances whilst the brighter values represent great distances. The euclidean distance between each pixel with coordenates I l (x, y 1 ) or I r (x, y 1 ) and the closer right edge (d 2 ), considering images of X × Y resolution and a maximum level of expected disparity equal to d max is computed via equations 5 -6; where β represents the value of threshold to determine an edge. δ is defined as l or r for the left or right images, respectively. z ranges from 0 up to d max . y 1 ranges from 1 up to Yd max and g 1 is defined by equation 7. In Figure 4 the distance to the closer right edge for all the pixels that integrate the Venus scene is shown. In order to determine the similarity between the distances to the edges d l , d r of the left and right images, I l and I r , it is proposed the use of the equation 8; where k is defined as {l, r} and z ranged from 0 up to d max .

d 2 (x, y 1 , z) = l = 0, k 2 (x, y 1 , z) < β l = l + 1, k 2 (x, y 1 , z) > β (5)
k 2 (x, y 1 , z) = |I δ (x, y 1 + z) -I δ (x, y 1 + g 2 + z)| (6)
g 2 = 1, y < X 0, otherwise (7)
D k (x, y, z) = |I l (d k (x, y, 0)) -I r (d k (x, y, z))| (8)

Fuzzy Inference System

The three similarity parameters, correlation (Crl) and the edge distances similarities (D l , D r ), ineherent to each (x, y) pixel for each z level of disparity, are submited to a fuzzy inference system that determines a fuzzy-similarity value. In the proposed fuzzy inference system, input membership functions for Crl, D 1 and D 2 are used. These functions determine the degree of truth to the fuzzy sets good , medium and bad, that represent the degree of similarity between the pixels of the left and right images, being good a high value of similarity, bad a low value of similarity and medium an intermediate value between high and low similarity.

Due to the linearity of the input data it is proposed to use triangular type functions with binary based slopes. Functions of this type allow to simplify the products and quotients to an shift operation over registers. This will be useful when implementing the proposed method in FPGA devices, this allow to reduce the hardware resources demand and maintaining low mathematical complexity. The input membership functions of for the good, medium and bad sets were defined as shown in equations 9 -11; where α, β and γ are equal to 0, 128 and 255 respectively. h corresponds to the similarity parameters values.

µ good (x, y) =            0, γ ≤ h h-γ α-γ • (255), α < h < γ 255, h ≤ α (9)
µ medium (x, y) =            h-α β-α • (255), α < h < β h-γ β-γ • (255), β ≤ h < γ 0, otherwise (10)
µ bad (x, y) =            0, h ≤ α h-α γ-α • (255), α < h < γ 255, γ ≤ h (11)
In the proposed method the output with the larger numerical value regarding to the diferent z disparity levels. In order to assign output values three fuzzy output sets are proposed good, medium and bad. Where good represents the major numerical output values, descending to the values pertaining to the medium set and finally the values from the bad set that represents the minimum numerical values that can define the output. The degrees of truth to these sets are determined via the functions ψ good , ψ medium and ψ bad , equations 12 -14; where α, β, γ, ρ and σ are equal to 0, 128, 255, 96 and 160 respectively.

ψ good (x, y) =            0, γ ≤ h h-γ α-γ • (255), α < h < γ 255, h ≤ α (12)
ψ medium (x, y) =            h-ρ β-ρ • (255), ρ < h < β h-σ β-σ • (255), β ≤ h < σ 0, otherwise (13)
ψ bad (x, y) =            0, h ≤ α h-α γ-α • (255), α < h < γ 255, γ ≤ h (14)
To relating the input sets to the output sets, the use of rules IF-THEN type and the AND operator of Zadet is proposed [START_REF] Zadeth | Fuzzy sets[END_REF]. The design rules are shown in the Table 1. In order to use a fuzzy inference process with low hardware resource consumption, it is proposed the following fuzzy inference mechanism. First, the precedent of each rule is computed replacing the numerical values of the Crl, D 1 and D 2 inputs in equations 9-11; where ε n (x, y) is the precedent of the nth rule and µ 1 (x, y), µ 2 (x, y) are both fuzzy sets included in each rule (Table 1). On the other hand, the consequent to each rule is determined as shown in equation 16; where ϑ n (x, y) is the consequent of the nth rule. inp is the input value for the corresponding similarity parameter and f s is an point-slope type equation that describes a linear segment of the output membership functions, equations 12-14. In the column f r of the Table 1 the assignation of functions f s for each rule is shown. Finally, the result of the fuzzy inference is determined using the Mean-Max method, equation 20; where ϑ m1 (x, y), ϑ m2 (x, y) are the consequence of the two rules with higher implication in the fuzzy inference process while the corresponding disparity value is determined via the equation 21.

ε n (x, y) = min (µ 1 (x, y), µ 2 (x, y)) (15)
ϑ n (x, y) = f s (ε n (x, y)) (16)
f 1 (ε n (x, y)) = ε n (x, y) (17)
f 2 (ε n (x, y)) = -ε n (x, y) + 255 (18)
f 3 (ε n (x, y)) = (ε n (x, y) -768)/8, inp < 128 (-ε n (x, y) + 1280)/8, otherwise (19)
fuzzy inference(x, y, z) = (ϑ m1 (x, y) + ϑ m2 (x, y))/2 [START_REF] Kumar | Stereo matching algorithms based on fuzzy approach[END_REF] disparity(x, y) = arg max z fuzzy inference(x, y, z)

Output mapping

In order to turn the disparity values defined by values from 0 up to (d max ) to RGB values with 10 bits of depth, it is proposed to applying the equation 22; where d max is the maximum expected disparity value ∀ η {1, 2, 3}. disparity mapped (x, y, η) = disparity(x, y) * 1023/d max [START_REF] Zitnick | A cooperative algorithm for stereo matching and occlusion detection[END_REF]

Computational complexity

In order to explain the computational complexity of the proposed algorithm, first, the SAD computational complexity is analyzed. In this case the computational complexity is defined as following: O SAD (M S D/d ); where M is the size of the input stereo pair. S is the size of the correlation window. D is the maximum expected disparity and d is the increment regarding to the disparity values. Like SAD, the proposed algorithm possesses a computational complexity defined in the same terms, Table 3

. i.e. O SAD = O propoed = O(M S D/d ).
Based on the high efficient of to the SAD algorithm and considering that his computational complexity is equal to the complexity of the proposed algorithm. It is possible to affirm the high efficient of the proposed method.

On the other hand, although the proposed method possesses mathematical complexity similar to SAD, due to edges extraction, similarity computation stage and the fuzzy inference process, the runtime is increased. In Table 2 the runtime of the SAD algorithm considering different synthetic stereo pairs and different values for the maximum expected disparity compared with the proposed method runtime considering similar settings is presented. As can be seen, in all the cases an increment of the runtime is observed, near to 10 times. However, most of the new runtime corresponds to the fuzzy inference process. In MatLab this is an iterative process that computes in sequential form the degree of truth for all the input fuzzy sets. Then evaluates in sequential form all the fuzzy rules and assigns the corresponding antecedent and consequent values. Finally the fuzzy similarity value is computed. However, this process could be parallelized when the proposed method is implemented in dedicated hardware such as FPGA devices that enables to reach real-time processing. Furthermore, considering the proposed fuzzy inference method any FPGA architecture must maintain low hardware resources consumption. Finally, in Table 3 the detailed pseudocode for the proposed method is shown. As can be seen this consist into several recursive and sequential operations, such as edge extraction stage, edge similarity computation, fuzzy inference process and so on, characteristics that allow parallel-pipelined design suitable for FPGA devices. In Fig. 5, an overview of the developed FPGA architecture is shown. This architecture has three inputs. clk pixel as the pixel rate of the input stereo pairs. key [3:0] as as control signals for the left and right cameras and P [29:0] as input/output bus for the cameras. On the other hand, the developed architecture has one output, disparity [10:0], corresponding to disparity value for the selected pixel. The developed FPGA architecture was set to process input stereo pairs of 1200 × 1024 pixel resolution, and considering a maximum expected disparity equal to 15. Its general behavior can be described as following: first, the image acquisition modules capture stereo video streams. Then, the storage vector modules store gray scale values of pixels contained in 5 horizontal lines for both left and right images of input stereo pair. Later, the disparity value are computed via disparity computation module. Finally, the mapping convert the final disparity value to grayscale values of 10 bits of depth. In the following subsections the architecture of all the individual modules is shown in detail.

The image acquisition module

In order to acquire input stereo pairs, CCD sensors connected in a TRDB DC2 board is used. This board provides stereo pairs of 1280×1024 pixel resolution in RGB scale. In most of the FPGA stereo matching implementations reported in the literature, grayscale values with 8 bits of depth are used. However, the TRDB DC2 board provided images in RBG format with 10 bits of depth. Although the developed architecture could be configured to process 10 bits of depth, this increases the hardware resource consumption. In order to perform appropriate comparisons regarding to other methods, only the most significant 8 bits of the data provided by the TRDB DC2 board are used. On the other hand, in order to determine the grayscale value for the input images, the value of the green channel is used as grayscale value.

In Figure 6

The storage vector module

In order to store necessary data for the disparity computation, the use of the storage vector module is proposed. This module consists into five logic vectors. The size of four vector is equal to horizontal resolution×bits per pixel-1 while one vector size is defined as d max × bits per pixel -1.

Although the proposed module possesses similar behavior with respect to a shift register unit, this allows to read multiple data in one clock cycle. In general, when a image line begins, the gray scale value of the pixel with coordinate (1) is stored in index [7:0] of one storage vector, in the following clock cycle, this value is moved to index [15:8] and the gray scale value of the pixel with coordinate ( 2) is stored in index [7:0]. A similar process is repeated for all the pixels that integrate the line. In Figure 7, behavior of storage vector module with settings as follows: number of lines to process = 5, horizontal resolution = 1200. An pixel-parallel window-parallel architecture was designed. Using the appropriate indexes for the storage vector is possible to process the image to the video cadence, giving as result a disparity map of (Xw)*(Yw) pixels of resolution, where X, Y are the values of resolution of the input frames and 2w + 1 is the dimension of the correlation window used. In the following subsections, details regarding to the operation of the module disparity computation is shown.

The similarity parameter module

The similarity parameter module calculates the similarity parameters necessary to estimate the disparity value for one particular pixel, Crl(x, y, z), D l , D r . This module consists into three sub-modules implemented in parallel form. Furthermore, a 5×5 correlation window and maximum expected disparity equal to 15 are used. In order to compute the first parameter (Crl(x, y, z)); the first sub-modules performs the absolute difference between all pixels in the correlation window in parallel form. Then, all absolute difference values are summed.

The second sub-module computes the second similarity parameter D l . First, this sub-module applies the equations 3 and 4 and computes the k 1 value. The Figure 9 shows the position of the pixels used in this stage; by maintaining this position it is possible to compute the d l value at the video cadence. In addition, this figure shows a scenario in which the storage process for the five lines of the first correlation window have been completed; as can be seen the third vector correspond to the central line of the correlation. Due to shift behavior it is possible to compute the k 1 value at video cadence. After the k l value is computed , it is determines the d 1 value by assigning to β (equation 2) a constant value equal to 32. Finally, the similarity value between the edges of the left and right images is computed via equation 8. Finally, the third sub-module computes the third similarity parameter, D r . This sub-module possesses a similar behavior to the D l computation sub-module. First, it is applied the equations 6 and 7 and it is computed the k r value. After the k r value is computed , it is determines the d r value by assigning to β (equation 5) a constant value equal to 32. Finally, the similarity value between the edges of the left and right images is computed via equation 8. However, the storage vector module, Figure 7 only allows to determine the left edge distance values. In order to compute the right edge distance values it is proposed the use of the right direction vector module.

The right direction vector module

This module consist into three stages. First, it is determined when all the pixels from one line of the input frame are stored in the number 1 vector of the storage vector module, Figure 7. i.e., it is determined when the storage process for all the pixels of the line 1 or 2 or 3 and so on is completed. Then, in the second stage the values contained in the number 1 vector of the storage vector module are copied and placed in the k r vector, Figure 11-(a). The k r vector possesses a similar behavior to the vectors of the storage vector module, however, the order in the data of the k r are inverted. Using the k r vector it is possible to obtain the D r value. Finally, in the third stage the d r values are placed in the d r vector. The behavior of this vector is shown in the Figure 11-(b). This structure assigns the degrees of truth to the fuzzy input sets good, medium and bad for the three similarity parameters. Later, in the second sub-module the 18 rules that integrate the proposed bank of rules are evaluated in parallel form, the antecedent and consequent regarding to each rule are calculated according to the equations 15-16. Then, the 18 calculated consequent enter to the max third module that determines the two rules with higher implication in the inference process. Finally, the fourth module computes the arithmetic mean of its two inputs, defuzzification process. i.e. computes the fuzzy-similatity value.

The max module

In order to reach an appropriate propagation of the processed data, the use of the max actor is proposed, Figure 10. It consists into one index generator module and 5 maximum modules implemented in sequential form. First, the index generator module assigns the corresponding indexes to all the fuzzysimilarity values values from, then, the maximum 1 module, receives all the fuzzy-similarity values and their indexes. Af-terwards, this module determines the maximum values for correlation values, which are sorted by pairs with unrepeated correlation values for any pair; the minimum correlation values and their indexes obtained here are placed in logic vectors of type value [x:0], where x = 16×(d max +1)-1, and index [x:0], where x = 8 × (d max + 1) -1, respectively. This process is repeated in sequential form five times only one correlation value and its index are placed in the output vectors. At this time, the stored index are equal to the disparity value.

The mapping module

In order to display the calculated disparity maps a 4,3" LCD screen of 800x480 pixels of resolution of the terasIC brand was used. Due to the used screen operates with color values of 10 bits per pixel, the mapping module, Fig. 5, turns the disparity values, in this case velues ranged from 0 to 15, to grayscale values with 10 bits per pixel, equation 22. In order to reduce the hardware resources requirements the equation 22 was evaluated with disparity values from 0 up to 15 with increases equal to 1, the obtained values were integrated in a CASE structure which assigns disparity values with 10 bits per pixel.

Discussion and analysis of results

The architecture presented in Section 3 was implemented using a top-down approach. All modules were codified in Verilog and were simulated using post-synthesis simulations performed in ModelSim-Altera 6.6c in order to verify its functionality. Quartus II Web Edition version 10.1SP1 was used for the synthesis and FPGA implementation process. An FPGA Cyclone II EP2C35F672C6 embedded in an Altera DE2 development board was used. The hardware resource consumption for the developed FPGA architecture is shown in Table 5. In order to evaluate the performance of the proposed method, the developed architecture was analyzed using different values for the β parameter (equations 2, 5) and different sizes for the correlation windows. The tests were conducted using as test images the Tsukuba, Venus, Teddy and Cones scenes. β was evaluated using the values {8, 16, 32, 64, 128} while the window sizes used (2w + 1) were {3, 5, 7, 9, 11, 13, 15}. In the Figure 12 is observed the behavior of the error obtained in the disparity maps generated for different values of β considering 2w + 1 = 5. On the other hand, in Figure 13 the behavior of the error obtained in the disparity maps generated for different values of 2w + 1 considering β = 32 is shown. To determine the number of erroneous pixels, the corresponding disparity maps were submited in the website for evaluation of stereo systems of the Middlebury University [29].

In the Table 6 it is presented quantitative results of the number of erroneous pixels obtained by the proposed method for a correlation window of 5x5 (2w + 1 = 5) and β = 32 compared with other methods reported in the Literature. Disparity maps have been compared using the method proposed in [START_REF] Scharstein | A taxonomy and evaluation of dense twoframe stereo correspondence algorithms[END_REF] using the following configuration of images: Tsukuba (384×288, d max = 15), Venus (434×383, d max = 19), Teddy (450×375, d max = 59),Cones (450×375, d max = 59). In order to process and to collect the data presented in the Table 6, the developed architecture was scaled to operate with 64 levels of disparity. In Figure 14 the generated disparity maps for the proposed algorithm are shown. By analyzing Table 6, due to use of geometrical features such as edge distances the proposed algorithm allows high accuracy level in homogeneous areas, therefore, the results of the proposed algorithm improved most of SAD, SSD or NCC-based algorithms reported in literature, [31-33, 36, 37]. In addition, similar to most of stereo matching algorithms in the literature, the proposed algorithm has high performance with small values of maximum disparity (Tsukuba, Venus scenes) while medium performance with large values of maximum disparity (Teddy, Cones scenes). On the other hand, the proposed algorithm performance is lower than the census based algorithms, [START_REF] Martin Humenberger | A fast stereo matching algorithm suitable for embedded real-time systems[END_REF][START_REF] Stefania Perri | Adaptive census transform: A novel hardware-oriented stereovision algorithm[END_REF], however, census-based algorithms involve high mathematical complexity and the hardware resources requirements are high.

Table 7 presents comparisons of processing speed regarding to other real-time stereo matching algorithms reported in the literature. Due to the mathematical simplicity of the proposed algorithm, the developed architecture does not require complex arithmetical operations such as calculation of quotients and radicals (which require a high runtime), hence, it maintains high processing speed. When comparison of processing speed is conducted, Table 7, it is observed an increase with respect to other algorithms implemented in FPGA devices up to 78,725,120, minimum 14,417,920 pixels per second. In all cases except for the algorithm presented in [START_REF] Georgoulas | Fpga based disparity map computation with vergence control[END_REF],the processing speed for the proposed method is higher. However, considering the clock specifications for the algorithm described in [START_REF] Georgoulas | Fpga based disparity map computation with vergence control[END_REF], it is expected higher speed processing than the proposed algorithm. It is possible to affirm that if the same clock specifications are used, the proposed algorithm outperforms the speed processing for most of the FPGA-based stereo matching algorithms reported in the literature. Table 5 presents a comparison of the use of hardware resource regarding to other FPGA implementations in the literature. By analyzing the Figure 8, the higher performance for the proposed algorithm can be reached using a 5×5 correlation window. It is the main characteristic and difference regarding to all others stereo matching algorithms in the literature whose performance is proportional to the correlation window size. In order to reach high performance, large correlation window sizes are required. However, the correlation window size required for the proposed method is small, therefore, it is possible to decrease the hardware resource consumption, see Table 8. Finally, in Tables 9 and 10 present a comparison of the use of hardware resource regarding to all the synthesized and simulated configurations of the developed FPGA architecture. as can bee seen the hardware consumption for the developed FPGA architecture is appropriate for the majority of the low gamma of FPGA devices such as the Cyclone II family of Altera or Spartan II family of Xilinx. Low hardware resources requirements is useful in autonomous applications such as robotic applications, where the use of small FPGA devices that implies relatively few hardware resources is needed. On the other hand, due to high speed processing, low hardware resources consumption and high accuracy level compared with most of the FPGA implementations in the literature, any real-time application wich involve real-time stereo matching algorithms will take advantages by applying the proposed algorithm.

Conclusions

In this article, an area-based algorithm suitable for real-time stereo matching using similarity measures and geometric features was presented. Geometric features such as edge sitantaces allow high accuracy level in homogeneous areas. Then, in order to relate the similarity measures with the geometrical features, the use of a fuzzy inference system is proposed. Furthermore, in order to maintain low mathematical complexity suitable for FPGA implementations, a fuzzy inference mechanism based in point-slope equations is proposed. The main difference and advantage for the proposed algorithm is the use of small correlation windows in order to reach high accuracy level. Small correlation windows allow higher speed processing and lower computational resources requirement in comparison with the large correlation windows used in most of the SAD-based stereo matching algorithms reported in the literature.

In order to improve its processing speed, the proposed algorithm was implemented in a FPGA device. The developed FPGA architecture outperforms most of the real-time stereo matching algorithms in the literature, allowing high accuracy level and enables both increasing the processing speed and decreases the hardware resources consumption.

Finally, an important characteristic of the presented architecture is the scalability permissible; all the modules in the developed FPGA architecture, allow to be adapted for processing larger correlation windows than the simulated and implemented correlation windows. On the other hand, the FPGA architecture enables to configure different levels of maximum expected disparity (d max ), consequently, it is possible to configure the module for the computation of disparity maps with appropriate values to the environmental characteristics of the input video streams. This allows that the developed architecture can be applied to a wide range of applications of real-time stereo vision such as positioning systems for mobile robots and recognition, detection and so on.

Figure 1 :

 1 Figure 1: Block Diagram of the proposed method.

Figure 2 :

 2 Figure 2: Venus scene, left image.

Figure 3 :

 3 Figure 3: Venus scene, distance to the closer left edge.

Figure 4 :

 4 Figure 4: Venus scene, distance to the closer right edge.

2 : 16 End 10 : 20 End 11 :

 216102011 The size of an image I (H = X resolution × Y resolution ) W: The size of a correlation window (W = (2 × w + 1) 2 ) S : The maximum expected disparity (S = S m ) s : Increase of disparity (s = 1) Algorithm: Complexity: O(H W S /s ) For all pixels p(x, y) which satisfy x >= w, y >= w and x <= X resolutionw -S , y <= Y resolutionw For z = 1 with increments equal to s up to S 1: Compute the Crl(x, y, z) value, equation 1 End End For all pixels p(x, y) which satisfy x >= w, y >= w and x <= X resolutionw -S , y <= Y resolutionw For z = 1 with increments equal to s up to S Compute the d l (x, y, z) value, equation 2, δ=l 3: Compute the d l (x, y, z) value, equation 2, δ=r 4: Compute the D k (x, y, z) value, equation 8, k = l End End For all pixels p(x, y) which satisfy x >= w, y >= w and x <= X resolutionw -S , y <= Y resolutionw For z = 1 with increments equal to s up to S 5: Compute the d r (x, y, z) value, equation 5, δ=l 6: Compute the d r (x, y, z) value, equation 5, δ=r 7: Compute the D k (x, y, z) value, equation 8, k = r End End For all pixels p(x, y) which satisfy x >= w, y >= w and x <= X resolutionw -S , y <= Y resolutionw For z = 1 with increments equal to s up to S For n = 1 with increments equal to 1 up to 18 8: Compute the ε n (x, y) value, equation 15 9: Compute the ϑ n (x, y) value, equation Compute the fuzzy inference(x, y, z) value, equation Compute the disparity(x, y) value, equation 21 End For all pixels p(x, y) which satisfy x >= w, y >= w and x <= X resolutionw -S , y <= Y resolutionw 12: Compute the disparity mapped (x, y, η) value, equation 22 End

Figure 5 :

 5 Figure 5: General diagram of the developed FPGA architecture

  the detailed architecture of the image acquisition module is shown. The settings module send instructions regarding to the exposition and operation mode to the TRDB DC2 board, P [29:0]. The value of the exposition is defined via the Q [7:0] input while the operation mode is defied by the G [3:0], Table 4. The frame capture module consider the user settings S [15:0] and captures frames of 1280×1024 pixel resolution, obtaining at the D [7:0] output a binary chain with the RGB value form one pixel of the captured frame while the x [7:0], y [7:0] outputs consist on the indexes of each pixel. Finally, raw to grayscale enables to obtain grayscale values with 8 bits of depth, P [7:0] output.

Figure 6 :

 6 Figure 6: FPGA architecture for the stereo pair acquisition module.

Figure 7 :

 7 Figure 7: Behavior of the storage vector module

Figure 9 :

 9 Figure 9: Behavior of the storage vector module

Figure 8 :

 8 Figure 8: FPGA architecture of the disparity computation module

Figure 10 :

 10 Figure 10: Behavior of the storage vector module

Figure 11 :

 11 Figure 11: Pixels used to compute the D l value

Figure 12 :

 12 Figure 12: β parameter behavior.

Figure 13 :

 13 Figure 13: Behavior for different correlation window sizes.

Figure 14 :

 14 Figure 14: Disparity maps generated for different test images.

Table 1 :

 1 Bank of rules of the proposed fuzzy inference system

	Rule number	Crl	D 1	D 2	Output	f s
	1	good	good	none	good	f s = f 1
	2	good	medium	none	good	f s = f 1
	3	good	bad	none	medium	f s = f 3
	4	medium	good	none	medium	f s = f 3
	5	medium	medium	none	bad	f s = f 2
	6	medium	bad	none	medium	f s = f 3
	7	bad	good	none	medium	f s = f 3
	8	bad	medium	none	medium	f s = f 3
	9	bad	bad	none	bad	f s = f 2
	10	good	none	good	good	f s = f 1
	11	good	none	medium	medium	f s = f 3
	12	good	none	bad	medium	f s = f 3
	13	medium	none	good	bad	f s = f 2
	14	medium	none	medium	medium	f s = f 3
	15	medium	none	bad	medium	f s = f 3
	16	bad	none	good	medium	f s = f 3
	17	bad	none	medium	bad	f s = f 2
	18	bad	none	bad	bad	f s = f 2

Table 2 :

 2 Runtime for the proposed method

	Scene/Algorithm			Window size (2w + 1)
		3	5	7	9	11	13
	Tsukuba/SAD	7.48	9.32	11.5	14.2	16.9	21.2
	Venus/SAD	10.2	13.1	17.0	22.5	28.6	36.1
	Teddy/SAD	16.7	23.5	33.5	48.0	63.9	83.0
	Cones/SAD	16.7	23.5	33.5	48.0	63.9	83.0
	Tsukuba/proposed	79.5	99.3	123	154	193	241
	Venus/proposed	108	135	168	210	262	327
	Teddy/proposed	177	221	276	345	431	561
	Cones/proposed	177	221	276	345	431	561

*All the runtimes are measured in seconds and were obtained via MatLab implementations

Table 3 :

 3 Pseudo code for the proposed stereo matching algorithm

Table 4 :

 4 Operation specifications for the TRDB DC2 board

	Name	Description
	G 0	Reset the frame capture
	G 1	Assign the exposure value
	G 2	Pause the frame capture
	G 3	Continuous frame capture

Table 5 :

 5 Hardware resource consumption for the developed FPGA architecture.

	Resource	Demand
	Total logic elements	22,075 (66.89%)
	Total pins	161/475 (34%)
	Total Memory Bits	390,656 (81%)
	Embedded multiplier elements	0/70 (0%)
	Total PLLs	0/4 (0%)

Table 6 :

 6 Comparison between quantitative results for different real-time stereo matching algorithms.

	Method	Tsukuba	Venus	Teddy	Cones
	SAD	16.3%	28.5%	43.7%	39.8%
	[31]	12.0%	8.0%	-	-
	[32]	15.2%	14.1%	-	-
	[33]	12.8%	10.8%	10.7%	-
	[34]	6.2%	2.4%	13.8%	9.5%
	[35]	7.5%	4.1%	17.6%	18.4%
	[36]	10.4%	12.1%	29.1%	25.3%
	[37]	11.5%	5.27%	21.5%	17.5%
	Porposed	6.84%	6.07%	27.3%	22.4%

Table 7 :

 7 Processing speed for differents real-time stereo matching algorithms

	Method	Resolution	Frames/s	Pixels/s	Clock
	[33]	1024×1024	102	106,954,752	441MHz.
	[31]	1280×1024	65	85,196,800	246MHz.
	[34]	320×240	573.7	44,060,160	3GHz.
	[35]	640×480	68	20,889,600	120MHz.
	[36]	1280×1024	50	65,536,000	109MHz.
	[37]	640×480	230	70,656,000	245MHz.
	Proposed	1280×1024	76	99,614,720	100MHz.
	Proposed	450×375	592	99,900,000	100MHz.
	Proposed	434×383	601	99,899,422	100MHz.
	Proposed	384×288	904	99,975,168	100MHz.

Table 8 :

 8 Hardware resource consumption for different FPGA-based stereo matching algorithms

	Method	Logic Elements (LEs)	Memory bits (ALUTs)
	[33]	86,252	62,669
	[31]	89,459	84,307
	[35]	80,270	32 RAMs
	[36]	31,863	49,331
	[37]	53,616	60,598
	Proposed	22,075	48,832

Table 9 :

 9 Logic elements (combinational functions and logic registers) consumption for different configurations of the developed FPGA architecture

	a a d max	15	31	63
	resolution
	384x288	21,967 LEs	23,015 LEs	24,871 LEs
	434x383	22,003 LEs	23,621 LEs	25,457 LEs
	450x375	22,035 LEs	24,145 LEs	26,013 LEs
	1280x1024	22,075 LEs	24,450 LEs	26,487 LEs

Table 10 :

 10 Memory bits consumption for different configurations of the developed FPGA architecture

	a a d max	15	31	63
	resolution
	384x288	20,160 bits	20,296 bits	20,552 bits
	434x383	21,760 bits	21,869 bits	22,152 bits
	450x375	22,270 bits	22,408 bits	22,664 bits
	1280x1024	48,832 bits	48,968 bits	49,224 bits

Juan Antonio de Jes ús Osuna-Couti ño received the B.Eng. degree in Industrial Productivity in June 2011, Instituto Tecnológico de Tuxtla Gutiérrez, Tuxtla Gutiérrez, México. In June 2015 he received the M.Sc. degree in mechatronics engineering with highest honors, Instituto Tecnológico de Tuxtla Gutiérrez, Tuxtla Gutiérrez, México. His research interests are GPU algorithm acceleration, shortest path problem and fuzzy logic applications.


Madaín Pérez-Patricio

Abiel Aguilar-González

Efficient Similarity-based Adaptive Window Algorithm for Real-time Stereo Matching

Keywords: Adaptive window, Stereo matching, Disparity map, FPGA

The stereo matching is one of the most widely used algorithms in real-time image processing applications such as positioning systems for mobile robots, threedimensional building mapping and both recognition, detection and three-dimensional reconstruction of objects. In area-based algorithms, the similarity between one pixel of the left image and one pixel of the right image is measured using a correlation index computed on vicinities of these pixels called correlation windows. In order to preserve edges, small windows need to be used. On the other hand, for homogeneous areas, large windows are required. Due to only local information is used, matching between primitives is difficult. In this article, FPGA implementing of an efficient similarity-based adaptive window algorithm for dense disparity maps estimation in real-time is described. In order to evaluate the proposed algorithm behavior, the developed FPGA architecture was simulated via ModelSim-Altera 6.6c using different synthetic stereo pairs and different sizes for correlation window. In addition, the FPGA architecture was implemented in an FPGA Cyclone IIEP2C35F672C6 embedded in an Altera development board DE2. The disparity maps are computed at a rate of 76 frames per second for stereo pairs of 1280×1024 pixel resolution and a maximum expected disparity equal to 15. The developed FPGA architecture offers better results with respect to the most of real-time area-based stereo matching algorithms reported in the literature, allows increasing the processing speed up to 93,061,120 pixels per second and enables it to be implemented in the majority of the medium-gamma FPGA devices.

Introduction

The perception of the depht values of the points contained in a scene is one of the most important tasks of the computer vision systems and has been used in several applications such as positioning systems for mobile robots and both recognition, detection and three-dimensional reconstruction of objects [START_REF] Asadi | Delayed fusion for real-time vision-aided inertial navigation[END_REF][START_REF] Bartczak | Extraction of 3d freeform surfaces as visual landmarks for real-time tracking[END_REF][START_REF] Granados | On-chip semidense representation map for dense visual features driven by attention processes[END_REF].

Although numerous techniques exist to determine the depth of a scene, to extract the information referring to the depth from images obtained by a stereo configuration has become the most used technique. In this technique the correspondence between stereo pairs and the geometrical configuration of the stereo camera allows to obtain images of depth called disparity maps. In order to determine a disparity map it is necessary to measure the similarity of the points contained in the stereo pair. Techniques to determine these similarities are divided in two categories: area-based algorithms [START_REF] Aguilar-González | An fpga correlation-edge distance approach for disparity map[END_REF][START_REF] Jin | A fast and high quality stereo matching algorithm on fpga[END_REF][START_REF] Stefano | A fast areabased stereo matching algorithm[END_REF] and feature-based algorithms [START_REF] Feiyangcheng | Stereo matching by usingthe global edge constraint[END_REF][START_REF] Gong | Near real-time reliable stereo matching using programmable graphics hardware. Computer Vision and Pattern Recognition[END_REF][START_REF] Jung | Stereo reconstruction using high-order likelihoods[END_REF].

Area-based algorithm use the grayscale or color value of the surrounding pixels to the interest pixel for similarity stimation and produce dense disparity maps, i. e., they compute disparity for each pixel in stereo pair. These algorithms are more efficient in runtime, computer resource consumption and mathematical simplicity in comparison with features-based algorithms. On the other hand, feature-based algorithms are based on specific interest points and are more stable against changes of contrast, enviroment conditions and illumination due to they represent the geometric properties of the scene and the interest points are selected according to detectors of specific features. The main restriction of featurebased algorithms is that they do not allow to generate dense disparity maps, therefore, they often need to be applied with other techniques. In addition, a pre-processing stage for the extraction of features is necessary, which increases the computational resource consumption and runtime.

Due to FPGAs devices allow high speed handling of a large deal of information, several algorithms for the estimation of disparity maps have been implemented in these devices [START_REF] Isakova | Fpga design and implementation of a real-time stereo vision system[END_REF][START_REF] Jin | Fpga design and implementation of a real-time stereo vision system[END_REF]. Depending on the configuration of the cameras, the range of disparity levels varies; in the case of implemented algorithms in FPGA, this implies a significant increasement of the consumption of hardware resources, this has motivated diverse authors to study the possibility of reducing that disadvantage [START_REF] Kanade | A stereo machine for videorate dense depth mapping and its new applications[END_REF][START_REF] Murphy | Low-cost stereo vision on an fpga[END_REF] and search for new approaches to implement stereo vision algorithms in FPGA devices.

Related works

The system presented in [START_REF] Woodfill | Real time stereo vision on the parts reconfigurable computer[END_REF] consists in a 4×4 array of FPGAs connected in mesh type configuration, authors use a maximum total of near 35,000 LUT of 4 inputs, allowing to process 40 frames per second for images of 320×240 pixel resolution. In [START_REF] Darabiha | Reconfigurable hardware implementation of a phase-correlation stereo algorithm[END_REF], a structure based on four FPGAs Virtex 2000E of Xilinx is presented, obtaining dense disparity maps at a speed of 40 frames per second for images of 256×360 pixel resolution. In [START_REF] Diaz | Fpga based real-time opticalflow system[END_REF], the use of a single FPGA is proposed, the developed system processes images at 30 frames per second using images of 640×480 pixel resolution.

The architecture developed in [START_REF] Niitsuma | High-speed computation of the optical flow[END_REF], uses a technique based on SAD to calculate the optical flow efficiently, the system generates dense disparity maps at speeds superiors to 800 frames per second for images of 320×240 pixels using a correlation window of 7×7 and a maximum expected disparity equal to 121. A modification of SAD is shown in [START_REF] Lee | Real-time stereo vision on a reconfigurable system[END_REF], the authors of this work synthesize diverse versions of SAD to determine the needs and the performance of the hardaware resources, by decomposing the correlation window of SAD in rows and columns using buffers a saving of resource of around 50% is reached. Using different forms of windows, the high consumptions of memory decreases without any detriment of the quality. Disparity maps are calculated at speed of 122 frames per second for images of 320×240 pixels and a maximum expected disparity equal to 64.

The architecture in [START_REF] Masrani | A real-time large disparity range stereo-system using fpgas[END_REF] uses four FPGAs to conduct a rectification in real-time, later, a verification of left-right consistency was applied in order to improve the quality of the produced disparity map. Speeds of 30 frames per second are reached for images of 640×480 pixel resolution and a maximum expected disparity equal to 128. In [START_REF] Aguilar-González | An fpga correlation-edge distance approach for disparity map[END_REF] an FPGA correlation-edge distance approach is proposed. Speeds of 76 frames per second are reached for images of 1280×1024 pixel resolution and a maximum expected disparity equal to 15. By using a geometric feature, the euclidean distance between the selected point and the nearest left edge, the developed FPGA architecture provides a improvement over others conventional correlation-based stereo matching algorithms.

In [START_REF] Georgoulas | Fpga based disparity map computation with vergence control[END_REF] one module for real-time disparity maps computation implemented in an FPGA Stratix IV of Altera is proposed, disparity maps are computed at a rate of 320 frames per second for images of 640×480 pixels and a maximum expected disparity equal to 80. Finally, the module developed in [START_REF] Georgoulas | Real-time disparity map computation module[END_REF] enables to process 275 frames per second for images with a maximum expected disparity equal to 80 and 640×480 pixel resolution, the presented architecture provides a high speed of processing at expenses of the accuracy with great scalability in terms of disparity levels.

Adaptive window algorithms

Several adaptive algorithms have been proposed to improve results in both depth discontinuities and homogeneous areas. A technique of adaptive window in combination with SAD is used in [START_REF] Roh | Symmetrical dense disparity estimation: algorithms and fpgas implementation[END_REF], the algorithm processes images of up to 1024×1024 pixels and a maximum expected disparity equal to 32 at 47 frames per second. Authors of [START_REF] Kanade | A stereo matching algorithm with an adaptive window: Theory and experiment[END_REF] estimate the current depth by changes correlation window size and shape. These changes were performed iteratively according to the local variation of the gray scale values. However, the algorithm is computationally expensive and sensible to the initial depth estimates. Autors of [START_REF] Veksler | Stereo matching by compact windows via minimum ratio cycle[END_REF] have changed the window size and shape by optimization over a large class of compact windows via minimum ratio cycle. The algorithm presented in [START_REF] Lotti | Correlation algorithm with adaptive window for aerial image in stereo vision[END_REF] proposes using edges in the reference image to determine the size of a rectangular window. In [START_REF] Yang | A non-local cost aggregation method for stereo matching[END_REF], pixels are aggregated addaptively based on pixel similarity using a tree structure. In [START_REF] Min | Joint histogram-based cost aggregation for stereo matching[END_REF], obtain the aggregation process cost from a perspective of a histogram is proposed.

In order to simplify the adaptive algorithms, several algorithms have been proposed. Autors of [START_REF] Fusiello | Symmetric stereo with multiple windowing[END_REF] compute correlation coefficients on nine windows, and the one yielding the lowest value is retained. In [START_REF] Hirschmuller | Improvements in real-time correlationbased stereo vision[END_REF] the use of a central window surrounded by several support windows is proposed. The correlation coefficients of the best support windows, i.e., the lowest values, are added to the coefficient computed on the central window. The reduced number of windows used in these algorithms cannot cover the whole range of different sizes and shapes required in all the situations. The use of non-parametric measures has been proposed by autors of [START_REF] Zabih | Non-parametric local transforms for computing visual correspondence[END_REF], in the Census transform, each pixel and its surrounding is mapped into a vector of boolean variables, which denoting the ordering relation between the center pixel and a vicinity pixel. Boolean vectors are compared using the Hamming distance. Hamming distances are summed over a small local area and the shift that minimizes Hamming distance is retained as the disparity. Non-parametric measures reduces the sensitivity to outliers but not resolves the problem of the window size due to the window size must remain small. The main disadvantage regarding to the algorithms described in section 2.1 is that these can not be implemented in a dedicated hardware for real-time processing. However, in this research we are interested on stereo matching algorithms suitable for real-time image processing. The most adapted are correlation-based algorithms such as the sum of absolute differences (SAD), because they have a regular structure with fixed runtime. In addition, several systems that use correlationbased algorithms have been described in the literature.

In majority of area-based algorithms, a rectangular vicinity centered on a reference pixel in one of the images from a stereo pair is compared with similar vicinities for some pixels in the same raster line of the other image. Vicinities are called correlation windows and can be compared using a correlation-based measure such as SAD:

C l (x, y, s) = i=wx i=-wx j=wy j=-wy |I l (x + i, y + j)- I r (x + s + i, y + j)| ,
where I l (x + i, y + j) and I r (x + i + s, y + j) are the grey scale values of the pixels within the window in both images, called the left and right images respectively. (2 × w + 1) 2 is the correlation window size, s is the shift of the window in the right image and the maximal shift of the correlation window in the right image is s m . A correlation coefficient is determined for each pixel and the shift that minimizes the correlation coefficient is retained as the disparity. These algorithms yield a dense depth map, but they need a high runtime.

Disparity maps generated by applying the SAD algorithm on different synthetic stereo pairs are shown in Fig. 1. The main problem with this algorithm is to select the correlation window size. High window size values allow to determine the correct correlation values in areas with uniform texture. However, these window sizes imply a high computational demand and erroneous values at certain points due to the blurring edges and that small features are eliminated Fig. 1.(c),(f),(i). On the other hand, small window sizes imply low computational demand but the correlation coefficient measurement is sensitive to noise, hence, erroneous values at uniform texture regions are generated as seen in Fig. 1

.(b),(e),(h).

In order to avoid of the main disadvantages of the SAD algorithm (blurring edges and noise in homogeneous areas), the use of an adaptive correlation window based on a similarity criterion suitable for real-time image processing is proposed. Hence, in this article, an areabased stereo matching algorithm in which the size and shape of the correlation window are adjusted by each pixel in the reference image according to its content and his FPGA implementation are described. The proposed algorithm uses the grey scale values variations in the window as a technique to determine the similarity criterion. It is demonstrated that even with a simple similarity criterion, the proposed algorithm outperforms other adaptive window algorithms and enables to be implemented in a dedicated hardware for real-time processing such as FPGA devices. Furthermore, it is demonstrated that the developed FPGA architecture outperforms to the most of other real-time area-based stereo matching algorithms reported in the literature and allows to maintain a high processing speed.

The rest of this paper is organized as follows: section 4 presents the proposed algorithm and the technique to determine the similarity criterion used for the selection of pixels. In section 5, the FPGA architecture for the proposed algorithm is described. Experimental results for differents synthetic stereo pairs, a comparison with other adaptive window algorithms, a comparison regarding to several real-time stereo matching implementations reported in the literature and FPGA implementation results are detailed in section 6. Finally, section 7 concludes this article.

The proposed method

The main objective in this research is to develop one algorithm that uses a single window, which is processed only once using a recursive approach appropriate for dedicated hardware real-time proccesing implementation. In order to explain the proposed algorithm, the Tsukuba scene shown in the In the Similarity-Based Adaptive Window algorithm (SBAW), a fixed size window is centered on each pixel of the reference image, but only the selected pixels by similarity criterion are used to compute the correlation coefficient. Any correlation coefficient based on gray scale values can be modified using this technique. For example, the standard SAD expression turns into:

C l (x, y, s) = i=wx i=-wx j=wy j=-wy β(x, y, i, j) × ( 1
)
|I l (x + i, y + j) -Ir(x + s + i, y + j)| ,
where the coefficient β(x, y, i, j) is equal to 1 when the pixels from the correlation window are projections of the selected point, otherwise is zero. i and j are used in the sum process. This corresponds to define a window with variable size and shape that can be adapted to the local reference image data. In order that pixels within the window correspond to the same object than the selected pixel P l (x, y), a pixel P l (x + i, y + j) is included or excluded from the window according to a similarity criterion. If the two pixels are similar, β(x, y, i, j) is set to 1, otherwise is zero.

Techniques to define the similarity criteria

Several techniques are able to be used to define the similarity criterion. However, a technique based on recursive approach is more suitable in terms of computational efficiency and facilitates his hardware implementation. In this section a technique based on the comparison of the grey scale values is described. It is demonstrated that even a simple technique allows the use of adaptive windows achieving to increase the disparity map accuracy.

Criterion based on comparison of the grey scale values

We can assume that two pixels are not similar and they have different disparity, when there is a significant difference between their grey scale values [START_REF] Zhang | Stereo matching with segmentation-based cooperation[END_REF]. Then, we set β(x, y, i, j) to 1 only when the grey scale value p(x + i, y + j) is close to the grey scale value of the selected pixel p(x, y), i. e., if:

|p(x + i, y + j) -p(x, y)| ≤ T (x, y) , (2)
where T (x, y) is the maximum acceptable difference between the grey scale values. In practice, it is sufficient to assign the value of T ∀ p(x, y) as a constant value defined by the user. However, the problem is to determine an appropriate value for all points contained in the input stereo pair. By analyzing simulations performed in Matlab R2013a, it was determined that small values of T are most appropriate for points contained in regions near the edges while higher values of T are more suitable for regions which belong to the same object. On the other hand, it was determined that by assigning a constant value to T erroneous stimations occur in regions where due to the color of selected pixel, some pixels of to the same object are eliminated from the correlation window. Therefore, assigning to T a constant value does not ensure that an appropriate value for each point of the input stereo pair is used, furthermore, wrong stimations will be obtained at some points.

In order to compute T the use of the sum of absolute differences between the selected pixel and vicinity pixels is proposed. This value of T is adapted appropriately to most points contained in the stereo pair. i.e., in homogeneous areas in which it is supposed that all the points correspond to the same object, T is small and allows to avoid noise points and punctual features of the object. This enables to increase the accuracy of the correlation measure. On the other hand, when multiple objects are projected, the T value increases, however, this value allows to differentiate between the object that includes the selected point and others. Through multiple tests performed in Matlab it was determined that the minimum pixels required for an T accurate estimation are the pixels around the selected pixel, I l (x, y) (cf. Fig. 4, equation 4).

Finally, it was determined that in areas where the variation of the correlation window is high, mainly the points close to the corners of objects, T value is high and the disparity estimation accuracy decreases. Even with this limitation a high accuracy could be reached (cf. Fig. 4). In this case j = 1 and T could be defined as T = K, equation 4.

However, using a simple adequation it is possible to increase the accuracy level. Considering that when the selected point is a corner, T value is high and points of diferent objects would be include in the correlation window. Therefore, when T value is high, this value could be replaced with a smaller value that allows to differentiate between the object that includes the selected point and the others. Based on the assumption that into a large correlation window, multiple objects are projected, i.e., multiple corners are included. If the correlation window size increases, the number of projected objects and corners proportionally increases. We propose compute the T value adding a restriction parameter applicable on the corner points, equation 3. This parameter is computed as shown in equation 5 and enables to reduce the errors at corners and increase the general accuracy near to 2%. Fig. 5 shows some correlation windows for the Tsukuba scene using Equation 3. Although several techniques can be used to define the similarity criterion. We can affirm that even using a simple technique like the proposed in this article, any rectangular correlation window can be adapted to the local variations in the stereo pair. In standard algorithms, the disparity d l (x, y) is defined as the shift s giving the maximum (or minimum) value of the correlation values, equation 1. In order to detect occlusions, the left-right consistency is used. For each pixel, if the disparity d l (x, y) computed using the left image as a reference is equal to the disparity d r (x + S m , y) computed using the right image as the reference, equation 6, the solution is considered as correct. Otherwise the pixels are marked as occluded and the disparity can be computed with subpixel accuracy or be assigned as the minimum value between d l (x, y) and d r (x + S m , y). In this case the minimum value between d l (x, y) and d r (x + S m , y) will be used.

Computational complexity

In order to explain the computational complexity of the proposed algorithm, first, the SAD computational complexity is analyzed. In this case the computational complexity is defined as following: O SAD (M S D/d ); where M is the size of the input image. S is the size of the correlation window. D is the maximum expected disparity and d is the increment regarding to the disparity values. Like SAD, the proposed algorithm possesses a computational complexity defined in the same terms, Table 2

. i.e. O SAD = O SBAW = O(M S D/d ).
Based on the high efficient of to the SAD algorithm and considering that his computational complexity is equal to the complexity of the proposed algorithm. It is possible to afirm the high efficient of the proposed method. In addition, when SAD applying left-right consistency was implemented, the SAD runtime was similar to the proposed method runtime for the same setup, Table 1. As can be seen, the increment on the runtime, in all the cases near to 30%, is the time required for the T value computation.

The buffer module

In order to store necessary data for the disparity computation, the use of buffer modules is proposed. These modules allows to store the gray scale values corresponding to the pixels contained in n horizontal lines from an image and enables to read all stored lines in parallel. An overview of the FPGA architecture of the buffer module is shown in 3, the behavior of the state machine for the output w/r [n+1:0] is shown, the number of states is set as n + 1. n RAMs are in read mode while one RAM is in write mode for all the states at any time.

On the other hand, in Table 4 the behavior of the state machine for output address [9:0] is shown. The RAM module consists of a synchronous singleport ram unit, its general settings was set as: type = synchronous, width = 8, depth = 2048, operation type = single port, all the others parameters are defined as default. These parameters allow to store the gray scale values for each pixel contained in horizontal lines from images of up to 2048 horizontal resolution with 8 bits of color depth. The use of an RAM modules array enables to read the gray scale values of the pixels contained in n horizontal lines from an image, see Table 5 Table 5: Behavior of the array of RAM modules w/r [n+1:0] Read lines by RAM1,2,3,4,n

1000• • • -,-,-,- 0100• • • 1,-,-,- 0010• • • 1,-,-,- 0001• • • 1,2,3,- • • •0001 1,2,3,n 1000• • • n+1,2,3,n 0100• • • n+1,n+2,3,n 0010• • • n+1,n+2,n+3,n 0001• • • n+1,n+2,n+3,n+4 • • •0001 n+5,n+2,n+3,n+4
The n lines generator module reads the outputs from the RAM modules and determines which RAMs modules are in read mode at any time. In order to assign lines in the outputs of the n lines generator module in ascending form, i.e., pixel 1 [7:0] = input image line number l, pixel 2 [7:0] = input image line number l+1, pixel n [7:0] = input image line number l+n-1, the outputs from the RAM modules in read mode are assigned to the outputs of the n lines generator module as seen in Table 6, the first column corresponds to the output w/r [n+1:0] of the RAM driver module, the second column corresponds to the numbers of the RAM modules assigned to the outputs of the n lines generator module.

1000• • • 2,3,4,5,• • •,n 0100• • • 3,4,5,• • •,n,1 0010• • • 4,5,• • •,n,1,2 0001• • • 5,n,• • •,1,2,3 • • •0001 1,2,3,4,• • •,n-1

The storage vector module

To compute the disparity value via the SBAW algorithm, it is necessary to have stored the gray scale values of all the pixels from the correlation window. However, the buffer module only provides the gray scale values of one of the vertical lines of the correlation window at each time. In order to store the rest of the values efficiently, use of n register-based storage vectors is proposed. All storage vectors possess a similar behavior with respect to a shift register unit, however, these allow to read multiple data in one clock cycle. In general, when a line begins, the gray scale value of the pixel with coordinate ( 1) is stored in index [7:0] of one storage vector, in the following clock cycle, this value is moved to index [15:8] and the gray scale value of the pixel with coordinate ( 2) is stored in index [7:0]. A similar process is repeated for all the pixels that integrate the line. In Fig. 8, behavior of storage vector module with settings as follows: number of lines to process = n, v = 8 × n -1 is shown. In Fig. 9 the architecture of the storage vector module is shown. For the computation of the disparity map via the SBAW algorithm, a pixel-parallel and window parallel architecture was designed; the necessary data are obtained from the storage vector modules, using the appropriate indexes is possible to process video streams at real-time, giving as result disparity maps of (X -w) × (Y -w) pixel resolution, where X, Y corresponds to the values of resolution of the input video stream and (2 × w + 1) 2 is the size of the correlation window used.

The architecture of the SBAW module is presented in Fig. 9, its general behavior is described as following: first, the absolute differences modules compute the absolute difference between pixels from left and right images of the correlation window. This process is executed in each of the d max + 1 absolute differences modules, implemented in parallel, which are configured for expected disparity levels from 0 until d max , where each module process only one disparity level and computes the absolute differences only for pixels which are projections of selected pixel, i. e., all pixels belong to the same object, equations 3 -5. Then, the output of each of the absolute differences modules are sent to its corresponding adder module, in this step adder blocks compute the sum of the absolute differences for all pixels retained in the correlation window. Finally, the minimum module assigns the corresponding index for all correlation values, then, determines the minimum correlation value and set the disparity value as the index of the minimum correlation value. In the developed FPGA architecture, two SBAW modules were implemented in parallel form where the first module uses the left image as reference and the second module uses the right image.

The minimun module

In order to reach an appropriate propagation of the processed data, the use of the minimum module is proposed. It consists of an index generator module and k min modules implemented in sequential form. Firstly, the index generator module assigns the corresponding indexes to all the correlation values from the previous stage, then, the min 1 module, receives all the correlation values and their indexes. Afterwards, this module determines the minimum values for correlation values, which are sorted by pairs with unrepeated correlation values for any pair; the minimum correlation values and their indexes obtained here are placed in the vectors (value [x:0], where x = 16 × (d max + 1) -1, and index [x:0], where x = 8×(d max +1)-1), respectively. This process is repeated in sequential form until only one correlation value and its index are placed in the output vectors.

The equalizer module

In order that disparity values are appropriate for displaying in LCD screens or another output devices, the use of the equalizer module is proposed. This module convert the final disparity value to gray scale values through disparity [7:0]×256/d max . To reduce the hardware resource consumption, this process was performed with a CASE structure, which considers all expected disparity levels and turns the final disparity value into integer constant value corresponding to the previously described operation. The FPGA architecture presented in section 5 was implemented with a top-down approach. All the modules were programmed using Verilog, Quartus II Web Edition version 10.1SP1 was used for the synthesis process. In order to verify functionality of all the modules individually, post-synthesis simulation in ModelSim-Altera 6.6c were executed.

Simulation results

In order to evaluate the behavior of proposed algorithm, the developed FPGA architecture was simulated in Model Sim-Altera 6.6c using different synthetic stereo pairs and different sizes for correlation windows. The selected tests stereo pairs were the Tsukuba, Venus, Teddy and Cones scenes. The window sizes used were: {3, 5,

41}. In Fig. 12 the behavior of the error obtained in the disparity maps generated for different window sizes for the selected synthetic stereo pairs are shown, this demonstrates the effec-tiveness of the developed FPGA architecture. Disparity maps have been compared using the method proposed in [START_REF] Scharstein | A taxonomy and evaluation of dense two-frame stereo correspondence algorithms[END_REF], in which the percentage of pixels with a disparity error greater than one is computed. Three percentages are computed, one for all non-occluded pixels (nonocc), one for all pixels (all) and one for occluded pixels near depth discontinuities (disc). Performance for occluded pixels are not considered because no one algorithm compute occluded pixels explicitly.

On the other hand, Fig. 13 presents the error percentage of all pixels (all) for all evaluated synthetic stereo pairs obtained via SBAW algorithm compared with using the SAD algorithm. For the SBAW algorithm, if a small correlation window is used, error is more important than error for the SAD algorithm because some pixels of the window are not used and effective area of the used window is reduced. However, error in untextured areas is significantly reduced when a large correlation window is used. Error at discontinuities grows with the correlation window but it is smaller than the error for the SAD algorithm. So, we can affirm that performance of the SBAW algorithm is better when a large correlation window is used. In Table 7 quantitative results of the number of erroneous pixels obtained by the proposed algorithm for the Tsukuba, Venus, Teddy and Cones scenes, using a 41×41 correlation window compared with other real-time stereo matching algorithms, reported in the literature, are presented. In order to process and collect the data presented in Table 7, the developed architecture was scaled and synthesized to operate with the appropriate maximum expected disparity values. For all cases, Quartus II Web Edition version 10.1SP1 was used for the synthesis process and simulations in ModelSim-Altera 6.6c were executed. By analyzing Table 7, it is observed that the results of the algorithm present a improvement regarding to the most of real-time-stereo matching algorithms reported in literature. In addition, similar to the majority of these algorithms, the proposed algorithm presents a high performance with small values of maximum disparity (Tsukuba, Venus scenes); whilst, a medium performance with high values of maximum disparity (Teddy, Cones scenes) is observed. The generated disparity maps for the Tsukuba, Venus, Teddy and Cones scenes considering 2 × w + 1 = 41 are shown in Fig. 14. Furthermore, comparisons with respect to other adaptive window algorithms, such as the SMW algorithm [START_REF] Fusiello | Symmetric stereo with multiple windowing[END_REF], the Census algorithm [START_REF] Zabih | Non-parametric local transforms for computing visual correspondence[END_REF] and the Hirschmüller (HIR) algorithm [START_REF] Hirschmuller | Improvements in real-time correlationbased stereo vision[END_REF], were performed. In order to perform comparisons, the synthetic image shown in Fig. 15 In the areas corresponding to a single object, all the algorithms estimate the disparity precisely, because the correlation window is large, however, the averaging effect generates errors at depth discontinuities, which is clearly visible in the disparity maps of the SMW and HIR algorithms (Fig. 16(a) and(b)). The HIR algorithm reduces errors at discontinuities, but there are still false matchings due to the central window, which is always used. Square windows used in the SMW algorithm are well adapted for this image. However, there are false matchings at the corners of the central square object. The performance of the Census algorithm is worse because of the repetitive pattern in the image. With the SBAW algorithm (Fig. 16(d)), the estimated disparity map is very similiar to the ground truth, even near of both depth discontinuities and at the corners of the central square object. Table 10 shows the numerical values obtained by perform this comparison. All values shown in this table were obtained by Matlab implementations for the HIR, SMW and Census algorithms. The erroneous pixels were measured by applying the equation 7; where I 1 is the ground truth map. I 2 is the generated disparity map by a particular algorithm. x is the horizontal resolution of the input image. y is the vertical resolution of the input image and N is set as x × y. In all the cases a similar setup was applied and similar behavior for different test escenes was observed. In Table 10 only two percentages are computed, one for all the pixels and one for the pixels near discontinuities, because objects are well textured. The quantitative comparison demonstrate that the error percentages increase with window size for SMW and HIR algorithms, but decrease with window size for the SBAW algorithm. In the SMW algorithm, the window is adapted according to the local texture as confirmed by the low error percentages, but a large window is not well adapted at the corners and the error percentages rise up with the size window. Percentage errors in the Census algorithm are high due to the repetitive patterns in the image, but their performance in discontinuities is better than the HIR algorithm. Applying SBAW algorithm using a small window, errors are caused by a lack of information in the correlation window. On the other hand, with large windows, the errors near to depth discontinuities are avoided with the SBAW algorithm. This behavior is confirmed by low error percentages of the SBAW algorithm for pixels near to depth discontinuities. For the SBAW algorithm, the best performance is obtained with a large window. This is a difference and an advantage with respect to the others algorithms where the window size must remain small. Tables 8-9 present a comparison of the use of hardware resource regarding to all the synthesized and simulated configurations of the developed FPGA architecture. By analyzing Fig. 12, the acceptable behavior for the SBAW algorithm can be determined by using a 21×21 correlation window, in this case the hardware consumption for the developed FPGA architecture is appropriate for the majority of the medium gamma of FPGA devices such as the Stratix III family of Altera or Spartan III family of Xilinx, however, for higher window sizes only high gamma FPGA devices such as the Stratix V family of Altera support the hardware resource consumption. It is the user decision to select the configuration of the SBAW algorithm more appropriate to his particular requirements.

σ = 2 1 N i=x,j=y i=1,j=1 (I 1 (i, j) -I 2 (i, j)) 2 (7)
Finally, Table 11 presents comparisons of processing speed regarding to other real-time stereo matching algorithms reported in the literature. Due to the mathematical simplicity of the proposed algorithm, the developed architecture does not require complex arithmetical operations such as calculation of quotients and radicals (which require a high runtime), hence, it maintains a high processing speed. When comparison of processing speed is conducted, Table 11, it is observed an increase with respect to other algorithms implemented in FPGA devices of up to 93,061,120 pixels per second.

Implementation results

The developed FPGA architecture was implemented in a FPGA Cyclone II EP2C35F672C6 embedded in the development board DE2 of Altera and the selected configuration for the SBAW algorithm was d max = 15, 2 × w + 1 = 15. In order to acquire input stereo pairs, a TRDB DC2 board connected in the first port of expansion of the DE2 board is used. TRDB DC2 board provides stereo pairs of 1280×1024 pixel resolution in RGB scale. In order to determine the gray scale value of the input stereo pairs, the value of the green channel was used as a gray scale value. With the purpose of reaching appropriate values to the environmental characteristics of the input scene, the implementation enables to configure the exposition of the cameras. For assigning the exposure value of the cameras, 4 push buttons of the DE2 board are used. The function of each of these push buttons is detailed in the Table 12.

Table 12: Control of the board TRDB DC2

Output disparity maps was displayed in a terasIC 4,3" LCD screen of 800×480 pixel resolution connected to the second expansion port of the DE2 board. The processing speed of the FPGA implementation is equal to 76 fps (99,614,720 pixels/s) for the input stereo pairs of 1280×1024 pixel resolution. The resource consumption of the implemented architecture is shown in Table 13.

Conclusions

In this article, an area-based algorithm suitable for realtime stereo matching using an adaptive window technique based on a grayscale similarity criterion was presented. Only selected pixels are used in the window according to their similarity to the central pixel. Furthermore, a technique to determine similarity criterion has been described and it was demonstrated that even using a simple similarity criterion, the SBAW algorithm outperforms other adaptive window algorithms reported in the literature. The best performance of the SBAW algorithm was obtained with a large window appropriated for homogeneous areas. However, since the effective size and shape of the window were adaptive, blurring effects at discontinuities are avoided.

In order to improve its processing speed, the proposed algorithm was implemented in a FPGA device. The developed FPGA architecture outperforms other real-time stereo matching algorithms in the literature, allowing high accuracy level and enables both increasing the processing speed and to be implemented in the majority of the medium gamma FPGA devices.

Furthermore, an important characteristic of the presented architecture is the scalability permissible; all the modules and submodules which integrate the developed FPGA architecture, easily allow to be adapted for processing of larger correlation windows than the simulated and implemented correlation windows. On the other hand, the FPGA architecture enables to configure different levels of maximum expected disparity (d max ), consequently, it is possible to configure the module for the computation of disparity maps with appropriate values to the environmental characteristics of the input video streams. This allows that the developed architecture can be applied to a wide range of applications of real-time stereo vision such as positioning systems for mobile robots and recognition, detection and tri-dimensional reconstruction of objects.

20 Fig. 1 :

 201 Fig. 1: Disparity maps generated for different test synthetic stereo pairs by applying the SAD algorithm

Fig. 2 .

 2 (a) is used. This image presents multiple objets at differents depths. Depth of each object is indicated using grey scale values as shown in the Fig. 2.(b). a) Original image b) Ground truth

Fig. 2 :Fig. 3 :

 23 Fig. 2: Tsukuba scene

T 21 Fig. 5 :

 215 Fig. 4: γ behavior, w = 21

  Cr(x, y, s) = i=wx i=-wx j=wy j=-wy β(x, y, i, j) × (6) |Ir(x + i, y + j) -I l (x -s + i, y + j)| ,

1 : 2 : 3 : 4 : 6 : 7 : 8 :End 9 :Fig. 6 :

 123467896 Fig. 6: General diagram of the developed FPGA architecture

Fig. 7 .

 7 This module consists of three different sub-modules, The RAM driver module manages an array of n + 1 single-port ram units (RAM) assigning to each one the corresponding address, address [9:0], and the corresponding write-read value, w/r [n+1:0]. The w/r [n+1:0] output consist of one logic vector of n + 1 bits of size, the write-read value of each of the RAMs is determined by each one of the bits of the w/r [n+1:0] output. The outputs of the buffer modules are determined via state machines, which are controlled by horizontal resolution of the input stereo pairs, x resolution [11:0], and the correlation window size n [5:0]. In Table

Fig. 7 : 1 0 2

 710 Fig. 7: FPGA architecture for the buffer module

Fig. 8 :Fig. 9 :

 89 Fig. 8: Behavior of the storage vector module

Fig. 10 :

 10 Fig. 10: FPGA architecture for the SBAW module

Fig. 12 :

 12 Fig. 12: Behavior of the developed FPGA architecture

  (a) Tsukuba and Venus scenes (b) Teddy and Cones scene

Fig. 13 :

 13 Fig. 13: Comparison between the SBAW algorithm and the SAD algorithm for all the erroneous pixels (all)

  (a) is used. Two textured objects are present in the synthetic scene, which appear as a square and as the background in the image. Fig.15(b)shows the ground truth map, where well defined edges correspond to depth discontinuities.

Fig. 15 :

 15 Fig. 15: Test scene stereo pair

Fig. 16 : 20 Fig. 14 :

 162014 Fig. 16: Results for the test scene (2 × w + 1 = 27)

Table 1 :

 1 Runtime for the proposed method

	Scene/Algorithm		Window size (2 * w + 1)
		9	25	49	81	121	169
	Tsukuba/SBAW	22.4	27.7	35.1	42.7	50.4	57.1
	Venus/SBAW	31.3	38.9	50.6	66.1	83.4	114
	Teddy/SBAW	46.3	66.4	98.7	138	191	252
	Cones/SBAW	46.3	66.4	98.7	138	191	252
	Tsukuba/SAD	15.3	17.6	20.9	25.3	30.8	40.6
	Venus/SAD	22.7	27.1	33.6	41.4	58.5	79.6
	Teddy/SAD	39.5	55.2	79.0	117	155	162
	Cones/SAD	39.5	55.2	79.0	117	155	162

*All the runtimes are measured in seconds and were obtained via MatLab

Table 2 :

 2 Pseudo code for the Similarity-Based Adaptive Window algorithm (SBAW)

Table 3 :

 3 Behavior of the state machine for the w/r [n+1:0] output of the buffer module

	State	Behavior
	1	If address < x resolution [11:0] and state = 1 then w/r [n+1:0] = • • •00001 else state = 2
	2	If address < x resolution [11:0] and state = 2 then w/r [n+1:0] = • • •00010 else state = 3
	. . .	. . .

n+1 If address < x resolution [11:0] and state = n+1 then w/r [n+1:0] = 1000• • • else state = 1

Table 6 :

 6 Output assignment for the n lines generator module

	w/r [n+1:0]	Assignment pixel l [7:0] for l=1,2,...,n

Table 7 :

 7 Comparison between quantitative results of real-time-stereo matching algorithms

	Algorithm Tsukuba	Venus	Teddy	Cones
	[25]	11%	8%	-	-
	[14]	8.7%	8.6%	-	-
	[11]	12.0%	8.0%	-	-
	[12]	15.2%	14.1%	-	-
	[9]	12.8%	10.8%	10.7%	-
	[2]	8.8%	6.9%	30.2	43.4
	[3]	3.8%	2.12%	11.85	8.45
	[33]	7.5%	4.1%	17.6%	18.4%
	[35]	10.4%	12.1%	29.1	25.3
	[18]	11.5%	5.27%	21.5	17.5
	[10]	7.8	11%	21	16.8
	SBAW	7.6%	3.2%	13.6%	16.4%

Table 10 :

 10 Errors for the synthetic pair (in %)

			Non-occluded		Near discontinuities
	Algorithm		Window size			Window size
		15X15 21X21 27X27 15X15 21X21 27X27
	HIR [15]	2.24	3.51	5.01	27.32	33.05	35.63
	SMW [1]	0.53	0.86	1.4	8.9	12.38	16.49
	Census [39]	3.21	3.16	3.62	26.97	29.97	33.46
	SBAW	0.34	0.34	0.33	4.94	4.53	4.37

Table 8 :

 8 Logic elements (combinational functions and logic registers) consumption for different configurations of the developed FPGA architecture

	dmax a a 2w + 1	3	9	15	21	27	33	41
	15	7,375	47,286	119,991	143,988	165,586	182,144	191,252
	31	14,699	94,099	238,782	286,536	329,516	362,466	380,591
	63	29,104	186,316	470,400	561,610	645,851	710,434	726,757

Table 9 :

 9 Memory bits consumption for different configurations of the developed FPGA architecture

	dmax a a 2w + 1	3	9	15	21	27	33	41
	5	65,636	163,840	262,144	344,064	442,368	573,440	671,744
	31	65,636	163,840	262,144	344,064	442,368	573,440	671,744
	63	65,636	163,840	262,144	344,064	442,368	573,440	671,744

Table 11 :

 11 Processing speed for differents real-time stereo matching algorithms

	Algorithm	Resolution	Frames/s	Pixeles/s
	[11]	1280×1024	65	85,196,800
	[33]	640×480	68	20,889,600
	[3]	256×256	100	6,553,600
	[35]	1280×1024	50	65,536,000
	[10]	384×288	1250	138,240,000
	[18]	640×480	230	70,656,000
	[26]	320×240	574	44,083,200
	[9]	1024×1024	102	106,954,752
	SBAW*	450×375	592	99,900,000
	SBAW*	434×383	601	99,899,422
	SBAW*	384×288	904	99,975,168

*Operating frequency = 50 MHz

Table 13 :

 13 Hardware resource consumption for the FPGA implementation

	Resource	Demand
	Total logic elements	27,061/33,216 (81%)
	Total combinational functions	21,639/33,216 (65%)
	Dedicated logic registers	15,180/33,216 (46%)
	Total pins	161/475 (34%)
	Total Memory Bits	407,472/483,840 (84%)
	Embedded multiplier elements	0/70 (0%)
	Total PLLs	2/4 (50%)