Ali Fazli Yeknami

Atila Alvandpour
email: atila.alvandpour@liu.se

Low-Power Low-Voltage ΔΣ Modulator Using Switched-Capacitor Passive Filters

Keywords: Passive integrator, delta-sigma modulator, low-voltage, low-power, active-passive modulator, feedforward architecture

A low-voltage low-power fourth-order active-passive ΔΣ modulator with one active stage is presented. The input-feedforward architecture is adopted, which improves the voltage swing prior to the quantizer. This enables a simpler comparator design and cascade of three passive filters. The passive integrator, as an alternate option to its power-hungry active counterpart, and the non-idealities associated with it are investigated. The active integrator used at the input stage provides most of the loop gain, which suppresses the thermal noise from the succeeding stages and minimizes the non-idealities in the comparator, such as noise and offset. The active integrator employs a two-stage amplifier with load compensation, whose DC-gain is boosted by a partially bodydriven technique. The modulator, operated from a 0.7 V supply and clocked with 256 kHz sampling frequency, achieves 84 dB SNR and 80.3 dB SNDR over a 500 Hz signal bandwidth, while it dissipates only 400 nW power.

Introduction

Biomedical electronics including portable medical devices, ambulatory and in-site hospital equipments and body implantable devices, in particular, have gained significant attention in healthcare. Low energy consumption is one of the major design concerns for prolongation of the battery lifetime or other limited source of energy. The analog-to-digital converters (ADCs) are the key building blocks of such devices. Delta-sigma modulator is a powerful ADC technique because of its higher accuracy in low-speed applications (e.g., medical applications). Passive integrator, as an alternative to the power-hungry active integrator, is a significant approach in the design of low-power and low-voltage delta-sigma (ΔΣ) modulators for reducing the analog power consumption [START_REF] Yeknami | A 0.5-V 250-nW 65-dB SNDR Passive  Modulator for Medical Implant Devices[END_REF][START_REF] Chen | A 0.25-mW Low-Pass Passive Sigma-Delta Modulator with Built-In Mixer for a 10-MHz IF Input[END_REF][3][START_REF] Chen | Design and Analysis of a CMOS Passive ΣΔ ADC for Low Power RF Transceivers[END_REF][START_REF] Yousry | A Third-Order 9-Bit 10-MHz CMOS ΔΣ Modulator with One Active Stage[END_REF][START_REF] Das | A 4 th -order 86dB CT ΔΣ ADC with Two Amplifiers in 90nm CMOS[END_REF]. However, due to the lack of DC gain inside the passive filter (or integrator), the modulator is sensitive to noise coupling, thereby affecting the signal-to-noise ratio (SNR). Modulators in [START_REF] Yeknami | A 0.5-V 250-nW 65-dB SNDR Passive  Modulator for Medical Implant Devices[END_REF] and [START_REF] Chen | A 0.25-mW Low-Pass Passive Sigma-Delta Modulator with Built-In Mixer for a 10-MHz IF Input[END_REF] employ switched-capacitor (SC) gain-boosted passive filter to somewhat compensate for the lack of gain. However, achieving very high gain requires unrealistically large capacitive area as well as high sensitivity to parasitic capacitances [3]. In [START_REF] Chen | Design and Analysis of a CMOS Passive ΣΔ ADC for Low Power RF Transceivers[END_REF] no DC gain is used in the second-order loop filter. Instead, a three-stage preamplifier is exploited before the comparator to compensate for the gain, which is a power consuming solution.

Due to no gain, the signal experiences a large suppression inside the passive filter, making the comparator design a challenging task. The comparator non-idealities including noise, DC offset, and hysteresis directly limit the modulator resolution [START_REF] Yousry | A Third-Order 9-Bit 10-MHz CMOS ΔΣ Modulator with One Active Stage[END_REF][START_REF] Das | A 4 th -order 86dB CT ΔΣ ADC with Two Amplifiers in 90nm CMOS[END_REF]. The third-order modulator in [START_REF] Yousry | A Third-Order 9-Bit 10-MHz CMOS ΔΣ Modulator with One Active Stage[END_REF] makes use of the passive filter in the first and third stages and an active Gm-C filter in the middle stage in order to compensate for the loop gain and to mitigate the comparator's offset and noise. In addition, the Gm block is to isolate the two pole sectors from each other and to prevent inter-stage loading between them. The fourth-order active-passive modulator in [START_REF] Yeknami | A 0.7-V 400-nW Fourth-Order Active-Passive Delta-Sigma Modulator with One Active Stage[END_REF] utilizes a low-power amplifier topology in the first integrator, which can suppress the comparator nonidealities and the thermal noise from the succeeding passive stages, resulting in significant reduction of the capacitive area.

This chapter introduces a new approach for power reduction in the ΔΣ modulators. It describes the design of the basic passive filter and the non-idealities associated with it. The traditional passive modulators using cascade-of-integrators feedback (CIFB) architecture are briefly reviewed and their advantages and disadvantages are explained in details. Then, a fourth-order feedforward active-passive modulator is presented using only one active stage, which mitigates some of the fundamental problems associated with the traditional passive ADCs.

The input feedforward architecture has an extra path from the input of the modulator to the quantizer [START_REF] Roh | A 0.9-V 60-μW 1bit Fourth-Order Delta-Sigma Modulator With 83-dB Dynamic Range[END_REF][START_REF] Yao | A 1-V, 1-MS/s, 88-dB Sigma-Delta Modulator in 0.13-μm Digital CMOS Technology[END_REF]. This small architectural modification eliminates the signal component inside the loop filter; therefore the filter only processes the quantization noise [START_REF] Yao | A 1-V, 1-MS/s, 88-dB Sigma-Delta Modulator in 0.13-μm Digital CMOS Technology[END_REF]. This distinct feature of the feedforward modulator structure encourages the cascading of three power-efficient SC passive filters despite their large attenuation. Moreover, the voltage swing at the quantizer input is the sum of the input signal and the suppressed quantization noise (processed by the filter), which eases the comparator design without requiring any preamplifier circuit. Significant power reduction can thus be achieved due to (i) the reduced sampling clock frequency by employing a fourth-order active-passive loop filter; (ii) the removal of the power-consuming preamplifier prior to the comparator, unlike the traditional passive modulators with feedback architecture; (iii) the use of power-efficient passive integrators; (iv) the relaxed amplifier design requirements in the full input-feedforward modulator structure [START_REF] Roh | A 0.9-V 60-μW 1bit Fourth-Order Delta-Sigma Modulator With 83-dB Dynamic Range[END_REF][START_REF] Zhang | A 0.6-V 82-dB 28.6-μW Continuous-Time Audio Delta-Sigma Modulator[END_REF]; (v) an accurate and low attenuation passive adder for summation of the input and feedforward paths, and (vi) last, but not least, the reduced supply voltage helped to scale down the power consumption from digital blocks.

The rest of the chapter is organized as follows. Section 2 discusses the issues associated with the design of passive modulators using feedback structure. Section 3 describes both the architecture-level and circuit-level design of the proposed fourth-order active-passive modulator, followed by the simulation results in section 4. Section 5 presents the performance comparison of this modulator with respect to the previously reported passive modulators. The chapter is then summarized in section 6.

Fig. 1.

The linearized model of the 2 nd -order passive ΔΣ modulator using distributed feedback topology [START_REF] Yeknami | A 0.7-V 400-nW Fourth-Order Active-Passive Delta-Sigma Modulator with One Active Stage[END_REF] (Courtesy of IEEE)

Passive Modulator Design Using CIFB Topology

In this section we take a closer look at the challenges concerning the design of passive modulators implemented by the CIFB architecture. The CIFB topology has no forward connections to the quantizer input, unlike the CIFF topology, but requires internal digital-to-analog converters (DACs) which are fed back to the input and the intermediate filters. In other words, a fourth-order CIFB modulator topology needs four feedback DAC branches to each integrator's input, while a CIFF modulator structure needs only one feedback DAC from the output to the input. Thus, the DAC circuitry is much simpler in a CIFF modulator structure.

System-Level Considerations

The linear model of the second-order passive ΔΣ modulator with two-pole lowpass filter and single-bit quantizer is shown in Fig. 1. To determine the signal and noise transfer functions (STF and NTF), a linear model is used for the quantizer. It is a gain stage, G, followed by additive white quantization noise. The gain factor G in a conventional active modulator is estimated as unity [START_REF] Rabii | The Design of Low-Voltage, Low-Power Sigma-Delta Modulators[END_REF] assuming the integrators swing is maintained close to the reference voltage. In a passive modulator the signal swing at the quantizer input is much weaker than the reference level, due to the successive attenuation by the passive filters [START_REF] Yeknami | A 0.5-V 250-nW 65-dB SNDR Passive  Modulator for Medical Implant Devices[END_REF][START_REF] Chen | A 0.25-mW Low-Pass Passive Sigma-Delta Modulator with Built-In Mixer for a 10-MHz IF Input[END_REF][3], resulting in a non-unity G. This gain is lumped into the comparator input, according to Fig. 1, and is a function of the passive filter's pole location [3]. An estimate of this gain is given by [START_REF] Chen | A 0.25-mW Low-Pass Passive Sigma-Delta Modulator with Built-In Mixer for a 10-MHz IF Input[END_REF][START_REF] Chen | Design and Analysis of a CMOS Passive ΣΔ ADC for Low Power RF Transceivers[END_REF] in which the overall loop gain is approximated to be unity at half of the sampling clock frequency, fs/2. For an overall loop filter transfer function HT, the estimated G can be calculated as 1/|HT(fs/2)|. On the other hand, since the modulator is a nonlinear system, an accurate value of the quantizer gain can only be obtained from the nonlinear simulations [START_REF] Norsworthy | Delta-Sigma Data Converters: Theory, Design, and Simulation[END_REF]. For a simple passive filter shown in Fig. 2, the ideal transfer function can be given in the z-domain as

1 1 1 ) ( ) ( ) (        z z z V z V z H in out   (1)
where ρ = C/Cs. The low-frequency gain is unity and the -3 dB cut-off frequency can be calculated from equation (1) as

) 1 ( 2 3      s dB f f ( 2
)
where fs is the sampling clock frequency. Taking fs = 500 kHz, Cs = 2 pF, determined from the thermal noise requirement, and C = 128 pF, placing the -3 dB bandwidth around 1 kHz, the NTF and STF of the second-order passive modulator shown in Fig. 1 can be approximated as:

3 . 0 1 1 ) ( z z z z GH GH z NTF         (3) 2 2 2 2 41 . 1 38 . 2 1 02 . 0 3 . 0 1 ) ( z z z GH GH GH z STF       (4)
Figure 3 depicts the magnitude of the NTF and STF. As expected, the passive modulator suffers from the limited in-band quantization-noise suppression due to lack of gain in the passive loop filter, resulting in low SNR. Unlike the conventional active ΔΣ ADCs which has unity-gain STF at low frequencies, some signal attenuation is obtained in the passive modulator. As clearly seen, this attenuation (or loss) is -3.5 dB Fig. 3. The magnitude of NTF and STF of a 2 nd -order passive modulator with ρ = 64 [START_REF] Yeknami | A 0.7-V 400-nW Fourth-Order Active-Passive Delta-Sigma Modulator with One Active Stage[END_REF] (Courtesy of IEEE) at low-frequency, which can also be obtained by substituting z = 1 into STF equation (4). This is the fundamental problem of the passive filters and the major performance limiting factor in the passive modulators, which terminates to an extremely low voltage swing at the quantizer input. For the second-order passive modulator presented in [3], as an example, the integrators output swing is in the order of 10 mVrms and 100 μVrms, respectively, for a full scale (FS) input that the comparator has to detect it. A highly sensitive comparator is then required to distinguish the signal from the noise coupled inside the loop. Therefore, the comparator in this design employs a threestage preamplifier circuit in order to compensate for the required loop gain, dissipating a large amount of analog power in this block. To the best of our knowledge, most of the existing passive ADCs have been designed based on the CIFB topology [START_REF] Yeknami | A 0.5-V 250-nW 65-dB SNDR Passive  Modulator for Medical Implant Devices[END_REF][START_REF] Chen | A 0.25-mW Low-Pass Passive Sigma-Delta Modulator with Built-In Mixer for a 10-MHz IF Input[END_REF][3][START_REF] Chen | Design and Analysis of a CMOS Passive ΣΔ ADC for Low Power RF Transceivers[END_REF], which rely only on second-order loop filter. Cascading more than two passive filters is impractical because the very large signal attenuation inside the loop demands multistage power-consuming preamplifier circuit prior to the comparator.

Low-Voltage Compatibility

One of the most significant advantages of the passive filter is that it can function at very low supply voltage as long as the gate of the switches is driven adequately. Utilizing advanced switches developed to date, the switch overdriving problem can simply be alleviated. Low-VTH switch [START_REF] Roh | A 0.9-V 60-μW 1bit Fourth-Order Delta-Sigma Modulator With 83-dB Dynamic Range[END_REF][START_REF] Ishida | Managing Subthreshold Leakage In Charge-Based Analog Circuits With Low-VTH Transistors by Analog T-Switch (AT-Switch) and Super Cut-off CMOS (SCCMOS)[END_REF], gate-boosted [START_REF] Pun | A 0.5 V 74-dB SNDR 25-kHz Continuous-Time Delta-Sigma Modulator with a Return-to-Open DAC[END_REF][16] or boot-strapped switches [17] are several examples of such modern switches. Energy harvesting and biomedical implant systems are two applications where ultra low-voltage circuit design is compulsory and highly demanding. Conventional analog circuit topologies are no longer useful in these systems. Therefore, new circuit techniques have been developed recently, which have enabled ultra low-voltage operation of the  ADCs [START_REF] Pun | A 0.5 V 74-dB SNDR 25-kHz Continuous-Time Delta-Sigma Modulator with a Return-to-Open DAC[END_REF][16]. Body-input operational transconductance amplifiers (OTAs) and body-input gate-clocked comparator operating at 0.5 V in [START_REF] Pun | A 0.5 V 74-dB SNDR 25-kHz Continuous-Time Delta-Sigma Modulator with a Return-to-Open DAC[END_REF] eliminated the constraint on the threshold voltage. Moreover, inverter-based integrators were realized by overdrive voltages near the VTH in the modulator presented in [16] using a switched-capacitor (SC) biasing scheme, where charge pump clock boosting scheme were utilized for sufficient switch overdrive. These combinations have made it possible to develop a  modulator operated from a power supply below 0.3 V. Both modulator prototypes rely on power-hungry active integrators at which analog circuit design is a challenging task at such low supply voltages, due to the limited headroom and small available signal swing. For a given gm, a body-input OTA requires several times larger bias current than a typical gate-input OTA, thereby preventing the target modulator to achieve a high power-efficiency. In addition to charge-pump clock boosting, the inverter amplifier biased near VTH needs special biasing and common-mode feedback (CMFB) circuitries that can operate with a 0.25 V supply voltage, imposing circuit overhead and additional power consumption. An alternative approach for designing low-voltage low-power  modulator is the substitution of power consuming OTAs by the power-efficient passive integrators [START_REF] Yeknami | A 0.5-V 250-nW 65-dB SNDR Passive  Modulator for Medical Implant Devices[END_REF]3]. Despite the lack of gain and therefore larger sensitivity to noise coupling inside the loop filter, the passive integrators suggest significant power reduction and ability to operate at low supply voltages. A 0.7 V second-order modulator was implemented in [3] using a fully passive filter and the standard feedback topology. It only consumes 430 nW power while obtaining 70 dB peak SNR. Due to very low signal swings of the passive integrators, high dynamic range signals can be applied at the modulator input. Since digital power is the dominant source of the power consumption in the aforementioned design, scaling down of the power supply could significantly contribute in the overall power reduction. A 0.5 V fully passive modulator was presented in [START_REF] Yeknami | A 0.5-V 250-nW 65-dB SNDR Passive  Modulator for Medical Implant Devices[END_REF] based on the design in [3] using a charge-redistributed gain-boosted passive filter in the second stage, a body-driven gain-enhanced preamplifier prior to the comparator, and a low-voltage comparator circuit. The switch overdrive problem was mitigated by low-VTH transistors while the non-linear sub-VTH leakage current of the critical switches was suppressed by an analog T-switch scheme [START_REF] Ishida | Managing Subthreshold Leakage In Charge-Based Analog Circuits With Low-VTH Transistors by Analog T-Switch (AT-Switch) and Super Cut-off CMOS (SCCMOS)[END_REF]. The modulator achieves 71 dB peak signal-to-noise-and-distortion (SNDR) from a supply voltage of 0.5 V, while dissipating only 250 nW power. The attained figure of merit (FOM) is 86 fJ/convertion-step, where FOM is calculated as Power/(2 ENOB ×2×BW) with ENOB as the effective number of bits (or resolution) and BW as the input signal bandwidth.

Performance Limiting Factors

Here the main limiting factors that avoid the passive modulators from obtaining a high-resolution will be discussed. As mentioned before, the lack of gain and significant signal suppression inside the passive loop filter make the design of highresolution comparator a critical and challenging task. To revisit other issues concerning the comparator design, the linear model of a second-order single-loop modulator, shown in Fig. 4, is considered in which all the noise sources are specified. The baseband output signal can be approximated as:

2 1 2 1 1 2 1 H GH N H H N H N N X Y q Com      (5)
where H1 and H2 are the integrators transfer functions, N1 and N2 are their inputreferred noise, respectively, while NCom and Nq represent the comparator input referred noise and quantization noise. Since both filters have no DC gain, only quantization noise obtains some lowpass filtering, due to the loop gain G provided by the quantizer. On the other hand, for a certain SNR the thermal noise (kT/C noise) of the passive filters can be mitigated by scaling up the capacitors size (area penalty). However, NCom is the only noise term that is not subject to any attenuation at low frequencies simply because H1 and H2 have no gain. NCom is any non-idealities of the comparator including the thermal noise, low frequency 1/f noise, and offset voltage. To alleviate these non-idealities the passive modulator in [START_REF] Chen | A 0.25-mW Low-Pass Passive Sigma-Delta Modulator with Built-In Mixer for a 10-MHz IF Input[END_REF] utilizes a preamplifier whose input devices have a W/L ratio of 200μm/1.2μm, imposing about 0.5 pF at the comparator input. Moreover, in the passive delta-sigma ADCs due to no gain in the stages preceding the comparator, the offset of the overall ADC is defined by that of the comparator [START_REF] Chen | Design and Analysis of a CMOS Passive ΣΔ ADC for Low Power RF Transceivers[END_REF].

To alleviate the non-idealities of the comparator, several solutions have been tried in the past [START_REF] Yousry | A Third-Order 9-Bit 10-MHz CMOS ΔΣ Modulator with One Active Stage[END_REF][START_REF] Das | A 4 th -order 86dB CT ΔΣ ADC with Two Amplifiers in 90nm CMOS[END_REF] where at least one active stage was used to suppress the inputreferred noise and the dc offset.

To summarize, due to a very small signal swing at the quantizer input of the passive ADCs using CIFB topology, the comparator design is a crucial and difficult task, limiting the design scaling to higher-order modulator. In the following section, a fourth-order modulator will be presented that employs three successive passive filters using cascade-of-integrators feedforward (CIFF) topology, resulting in voltage swing improvement at the comparator input. As a result, the comparator design becomes simpler and no power-consuming preamplifier is involved.

4-th Order Active-Passive Modulator

In this section we describe both the architecture-level and circuit-level design of a fourth-order active-passive modulator using full feedforward topology.

Architectural Design

Full feedforward architecture has become popular in recent years for low-power and low-voltage modulator design [START_REF] Roh | A 0.9-V 60-μW 1bit Fourth-Order Delta-Sigma Modulator With 83-dB Dynamic Range[END_REF]- [START_REF] Yao | A 1-V, 1-MS/s, 88-dB Sigma-Delta Modulator in 0.13-μm Digital CMOS Technology[END_REF], [16]. We take advantage of this architecture to improve the voltage swing at the quantizer input, a drawback of the passive modulators using traditional CIFB topology. As a result, the comparator design becomes simpler and no preamplifier stage is required prior to the comparator.

Modulator Topology. Figure 5 shows the block diagram of the single-loop fourthorder modulator topology with single-bit quantizer. An active integrator is used in the first stage, while three SC passive filters are employed in the following stages. The passive filters were described using the transfer function given by equation ( 1). The feedforward branches are summed at the input node of the quantizer. The optimal coefficients of the designed modulator are calculated from the behavioral simulation and are summarized in

         z z z z z z z z z NTF (6)
The magnitude plot of the NTF is shown in Fig. 6. Behavioral simulation indicates that the signal amplitude at the quantizer input is 40 mV for a FS input, much lower than the reference voltage, 0.5 V in this design. Since the delta-sigma ADC is a nonlinear block, the equivalent gain of the quantizer can be directly calculated from the simulation. 5. Block diagram of the single-loop fourth-order full feedforward active-passive  modulator with one active integrator in the first stage [START_REF] Yeknami | A 0.7-V 400-nW Fourth-Order Active-Passive Delta-Sigma Modulator with One Active Stage[END_REF] (Courtesy of IEEE) Table 1. Modulator coefficients [START_REF] Yeknami | A 0.7-V 400-nW Fourth-Order Active-Passive Delta-Sigma Modulator with One Active Stage[END_REF] (Courtesy of IEEE)

Y X - DAC 1 1 1     z z   a 1 a 2 a 3 a 4 c 4 c 3 c 2 c 1 + + -k H 2 H 1 1 1 1    z z 1 1 1     z z   H 2 1 1 1     z z   H 2 Fig.
A local resonator feedback loop with a gain coefficient of k is used to move a pair of the NTF zeros to the edge of the signal band. In this way, some SNR improvement can be achieved.

Integrators Output Swing.

A behavioral simulation with -1.94 dBFS input signal is accomplished to show the integrators output swing and the summed voltage level at the quantizer input. The reference voltage is set to 0.5 V. It is worth to be mentioned that the signal component leaks to the loop filter, due to the attenuation by the passive summation network. As can be seen from Fig. 7, the largest swing is observed at the first integrator output, however it is still within 60% of the reference voltage. The reduced voltage swing enables the OTA, the most critical and power consuming block, to have a relaxed slew-rate requirement, hence low power consumption. The output swing at the succeeding passive integrators decreases continually. As the loop filter in a full feedforward topology ideally only processes the quantization noise [START_REF] Norsworthy | Delta-Sigma Data Converters: Theory, Design, and Simulation[END_REF], the continuous attenuation of the passive integrators does not harm the input signal. In contrast to the feedback or CIFB topology, the feedforward topology has a signal path from the modulator input to the quantizer. Therefore, the voltage level at the quantizer input is still large enough for the comparator to detect it without requiring a stringent preamplifier circuit. More details of circuit design are explained in the following section. One thing should be noted is that, since the single-bit quantizer is used, the integrators in the full feedforward architecture still contain the attenuated signal component, particularly in the first integrator.

a1 = 0.2 c1 = 2 a2 = 1 c2 = 3 k = 1/64 a3 = 1 c3 = 2 a4 = 1 c4 = 5

Circuit-Level Design

This section describes the overall modulator circuit and its building blocks.

Passive Filter Design. The passive filter used as integrator in the second to fourth stages was shown in Fig. 2. The larger ρ places the filter pole to a lower frequency, according to equation [START_REF] Chen | A 0.25-mW Low-Pass Passive Sigma-Delta Modulator with Built-In Mixer for a 10-MHz IF Input[END_REF]. Intuitively, the overall loop gain is distributed among the first active pole sector and the quantizer gain, while the low frequency DC gain of the passive integrators is unity.

The parameter ρ = C/Cs , in general, is selected so that the -3 dB cut-off frequency, calculated from equation (2), to be placed near the edge of signal bandwidth. The simulation demonstrates that the voltage swing at the quantizer input is almost constant for ρ ≥ 32, as shown in Fig. 8a. On the other hand, the parameter ρ can also be determined from the SNDR simulations, which consider both the quantization noise and distortion performance. The simulation result shown in Fig. 8b illustrates an optimal ρ of 64. The sampling and integrating capacitors are therefore selected as 0.25 pF and 16 pF, respectively. In practical implementation of the passive filter (Fig. 2), the parasitic capacitors introduced by the top and bottom plates of the sampling and integrating capacitors can influence the filter transfer function, low frequency gain and pole location, given by equations ( 1) and ( 2). Here we examine the effect of these parasitics on the filter's and  modulator performance. Considering the filter of Fig. 9a for which the most significant parasitic capacitors are lumped into CP, the filter transfer function given by equation ( 1) can be modified to

1 1 1 ) (        z z z H P    (7)
where ρ = C/CS and β = CP/CS. Compared to equation (1), the term β = CP/CS is excessive and is created because of the parasitic capacitor at the internal node. The integrator (filter) loss and -3 dB cut-off frequency can be calculated from equation [START_REF] Yeknami | A 0.7-V 400-nW Fourth-Order Active-Passive Delta-Sigma Modulator with One Active Stage[END_REF] as follows:

1 ) 1 ( 0      p s s p C C C z H A P (8) p s p s s dB C C C C C f f        2 3 ( 9
)
where A0P is the magnitude of Hp(z) at DC. Compared to equation ( 2), the net effect of the parasitic capacitor is the higher passband attenuation (DC gain of less than unity) as given by equation ( 8) and the shift of the -3 dB cut-off frequency to a higher frequency as given by equation [START_REF] Zhang | A 0.6-V 82-dB 28.6-μW Continuous-Time Audio Delta-Sigma Modulator[END_REF], which can degrade the quantization noise suppression. As an example, with fs = 500 kHz, CS = 2 pF, C = 64 pF and the estimated Figure 9b indicates that in the presence of CP the gain decreases from unity to 0.95, while the pole shifts from 2.4 kHz to 2.54 kHz. The results can also be verified by inserting the parameters into equations ( 8) and ( 9), showing a good agreement between the simulation results and calculations. Furthermore, the impact of parasitic capacitors of the passive filters on the overall performance of the designed fourth-order modulator was simulated. Figure 10 shows the power spectra of the modulator with 10 fF and 50 fF parasitic capacitors inserted in the internal node of the passive integrators of the second to fourth stages. The achieved simulated SNDR is 79.6 dB and 77.4 dB from 10 fF and 50 fF parasitic capacitors, respectively. The third and fifth harmonic distortions also grow by 3 dB when the parasitic capacitor value increases from 10 fF to 50 fF. Consequently, the implementation of the sampling and integrating capacitors of the passive filters is very important to avoid large internal parasitics.

Inter-Stage Loading. Another non-ideality which can influence the performance of the passive modulators is the inter-stage loading effect. To explain this, we consider the cascade of two basic passive filters, illustrated in Fig. 2, for the sake of clarity. Figure 12 shows the resulting 2 nd -order passive filter and its equivalent model in the sampling phase, Ф1. Clearly seen in Fig. 12b, there is charge-sharing between integrating capacitor C2 of the first stage and the sampling capacitor CS3 of the next stage. During the sampling phase, this charge-sharing may bring up a sampling error, and can reduce the integrator's accuracy. This phenomenon is also called inter-stage loading effect, i.e. the sampling capacitor of the following stage loads the previous stage. The sampled voltage corresponding to the time instance n at node x (Fig. 12b) can be written as [START_REF] Wang | A 0.5 V Feedforward Delta-Sigma Modulator with Inverter-Based Integrator[END_REF] One way to prevent the 2 nd -order filter (Fig. 12a) from the inter-stage loading is to fully isolate the two passive stages from each other by using a buffer or an active integrator in the middle [START_REF] Yousry | A Third-Order 9-Bit 10-MHz CMOS ΔΣ Modulator with One Active Stage[END_REF][START_REF] Das | A 4 th -order 86dB CT ΔΣ ADC with Two Amplifiers in 90nm CMOS[END_REF]. However, this is a power-consuming approach, which requires a power-hungry active integrator. Another practical solution to cope with this 10) approaches one. For instance, in the designed modulator C2 and CS3 are 16 pF and 0.25 pF, respectively. Thus, there is only 1.5% sampling error in the second passive filter, due to charge-sharing. To further decrease the error, relatively larger integrating capacitor C2 is required, which imposes area penalty and more attenuation. On the other hand, the value of C2 was obtained from the -3 dB bandwidth requirement given by (2). Clearly, there exist trade-offs among sampling error, pole location, attenuation and area.

) 1 ( ) ( 2 3 2 2    n V C C C n V out S x
Local Resonator. The purpose of the local resonator feedback loop used in the designed modulator is to move a pair of the NTF zeros to the edge of the signal band, improving the in-band noise shaping. The resonator creates a simple negative feedback loop with a gain coefficient k of 1/64. The resonator is simple to be realized using SC implementation (two switches and one small capacitor). Figure 11 shows the simulated output spectra with/without local resonator. A 5 dB SNDR improvement was achieved in this way at the expense of a small area penalty.

Partially Body-Driven Gain-Enhanced Amplifier. Several OTA topologies were designed and carefully analyzed [START_REF] Yaknami | Design of OTAs for Ultra-Low-Power Sigma-Delta ADCs in Medical Applications[END_REF][START_REF] Yeknami | A 2.1 μW 80 dB SNR DT Delta-Sigma Modulator for Medical Implant Devices in 65 nm CMOS[END_REF] for ultra-low-power delta-sigma modulators. Among them a two-stage load-compensated amplifier was selected because of its higher power-efficiency, rail-to-rail voltage swing, and minimal load for a balanced gain-bandwidth (GBW) and phase margin. While two-stage Miller amplifier and single-stage current-mirror OTA have been commonly used for low-power and low-voltage modulators [START_REF] Roh | A 0.9-V 60-μW 1bit Fourth-Order Delta-Sigma Modulator With 83-dB Dynamic Range[END_REF][START_REF] Yao | A 1-V 140-μW 88-dB audio sigma-delta modulator in 90-nm CMOS[END_REF], we exploit the two-stage load-compensated OTA topology because of its privilege in low bias current and low speed environment of the target medical application [START_REF] Yeknami | A 2.1 µW 76 dB SNDR DT Delta-Sigma Modulator for Medical Implant Devices[END_REF][START_REF] Yeknami | Low-Power Delta-Sigma Modulators for Medical Application[END_REF]. Due to low bias current (in the range of 100 nA) in this design, the output resistance of the OTA is intrinsically high and the dominant pole of the output load CL is then placed at very low frequency using a minimal load capacitor value (2 pF load). Therefore, in this low clock speed application the load compensation is preferred to the Miller compensation as it prevents additional power consumption for driving the Miller capacitor.

A fully-differential partially body-driven and gain-enhanced two-stage amplifier with load-compensation was developed for the modulator's input active stage. The detailed circuit is shown in Fig. 13. To reduce the power, the input common-mode level of the OTA is set to 0.35 V (i.e., VDD/2), which is limited by the gate-source voltage of M1a-M1b, and the drain-source voltage of M0. Low-VTH transistors are used to provide more headroom for the low-voltage analog design. Meanwhile, the bodies of the p-MOS transistors (i.e., M2, M3, and M6) are tied to half of the VDD (the common-mode level of the  modulator) to further decrease the threshold voltage, providing even more operating headroom.

The cascode topologies such as telescopic or folded cascode do not exist in lowvoltage analog design, which brings rail-to-rail voltage swing at the cost of restricted DC gain. A body-driven positive feedback is adopted at the output stage (M6a/M6b) to enhance the gain without significant power increase. The transistors M6a and M6b form a cross-coupled connection at their body terminals, which introduces negative

A         ( 11
)
The size of M6a/M6b is chosen such that the conductance gmb6 becomes 65% of the term gds3+gds4+gds5+gds6. With this option the amplifier is stable and gives high enough DC gain. As shown in Fig. 14, with gain-enhancement technique the typical DC gain and GBW increase from 39.6 dB and 670 kHz to 50.4 dB and 1.12 MHz, respectively. Figure 15 also shows the gain and phase plot of the OTA under process and temperature variations (-20°C to +85°C). The worst-case gain and GBW are 43 dB and 600 kHz, respectively, which are adequate for the target SNR, according to system-level simulations. Using typical simulations, the OTA achieves 50.4 dB DC gain, 60° phase margin and 1.2 MHz GBW with a 2 pF load, while dissipating 250 nW power.

Since for a given bias current the gm of the weak inversion transistor is almost five times larger than that of a strong inversion [START_REF] Tedja | Analytical and Experimental Studies of Thermal Noise in MOSFETs[END_REF], the main transistors (M1, M3, and M6) are driven in the weak inversion region, while other transistors are biased in the moderate inversion region. This can also help to decrease the thermal noise of the mentioned transistors that is represented by 2kTγ/gm1. Passive Adder. In the designed modulator a passive SC network is employed for the summation of the feedforward branches in order to avoid power consumption due to an active adder. However, careful design consideration is needed to prevent significant voltage attenuation prior to the quantizer. Figure 16 shows the used adder in its single-ended form. In Ф1 the input and integrators output are sampled onto feedforwarded capacitors Cf0-Cf4, while in Ф2 these capacitors are discharged. Using superposition principle and the voltage divider across CCom, the output voltage Vout can be expressed as

          4 1 4 4 ... 1 1 0 0 o Com o Com in Com Out V C Cf Cf V C Cf Cf V C Cf Cf V ( 12
)
where Vin+ is the positive input, Voi+ (i = 1-4) is the i-th integrator's output, and CCom models the parasitic capacitor at the comparator input. An important design consideration at this point is to keep the CCom a low value in order to avoid voltage attenuation. In the designed comparator, the estimated input parasitic is less than 100 fF. With this value and the capacitor values listed in Table 2, the output voltage given by ( 12) reduces to

          4 3 2 1 98 . 0 95 . 0 97 . 0 95 . 0 9 . 0 o o o o in Out V V V V V V ( 13
)
In the modulator block diagram shown in Fig. 5, it is assumed that the inputfeedforward coefficient (from input x to quantizer input) is unity. It can be shown that the corresponding STF is one in all frequencies. In modulator realization with passive

Ф1 Ф1 Cf4 Ф2 cm Ф2 cm V O4+ Ф1 Cf0 Ф2 cm V in+ Ф1 Cf1 Ф2 cm V O1+ C Com V Out Fig. 16.
Passive adder. Single-ended scheme is shown for the sake of simplicity.

Voi+ (i = 1-4)
is the i-th integrator's output, and CCom represents the parasitic capacitor at the input of the comparator adder shown in Fig. 16, however, the input-feedforward coefficient reduces to 0.9 rather than unity. As a result, the STF can be modified to

H H STF    1 9 . 0 (14)
It can be shown that the loop filter H is equal to 0.4H1+0.6H1H2+0.4H1 2 2

H +H1 3 2
H , where H1 is the transfer function of the first active integrator, and H2 is the transfer function of each passive integrator in the following stages (Fig. 5). For the sake of simplicity, the local resonator is omitted and is not considered in the function H. The magnitude plot of the STF is shown in Fig. 17. To summarize, the attenuation due to the passive summation is dealt with a low input parasitic capacitor in the designed comparator circuit. In turn, a power-consuming amplifier in an active adder is prevented, leading to a power-efficient modulator design.

Single-bit Quantizer. The existing passive ADCs [1-5] make use of the traditional CIFB architecture, which primarily suffer from the extreme signal suppression. This makes the comparator design a challenging task. The use of preamplifier stages, as a power consuming solution, prior to the comparator circuit is essential for detecting the very weak signal. As an example, 35% of the total power dissipation in the design presented by [START_REF] Yeknami | A 0.5-V 250-nW 65-dB SNDR Passive  Modulator for Medical Implant Devices[END_REF] comes from the preamplifier. The single-bit quantizer in this design is composed of a dynamic regenerative comparator followed by a SR latch [START_REF] Yao | A 1-V 140-μW 88-dB audio sigma-delta modulator in 90-nm CMOS[END_REF]. No pre-amplification stages were used, which lead to a significant power saving. The simple reason is that, compared to the traditional CIFB modulator architecture, the selected CIFF architecture relaxes the voltage swing requirement at the quantizer input. In other words, the voltage amplitude at the comparator input node of the designed feedforward modulator is the sum of the input signal, the first active integrator's output swing and the attenuated output swing from the succeeding passive integrators, which is relatively larger than that of a modulator implemented by a CIFB structure. This can be clearly seen in Fig. 7. We then utilize a simple and power-efficient quantizer circuit without pre-amplifications [START_REF] Yeknami | A 0.7-V 400-nW Fourth-Order Active-Passive Delta-Sigma Modulator with One Active Stage[END_REF]. The circuit schematic is shown in Fig. 18. When clock signal clk goes low, the nodes x and y are precharged to VDD. While clk goes high, the precharged nodes start to discharge to ground by transistors M1a and M1b. The amount of discharge currents depend on the input signals. The cross-coupled transistors, M3a and M3b, form a positive feedback loop and amplify the difference in the inputs to a full-rail output. As the comparator is a dynamic circuit and is clocked by the non-overlapping clock phases, a slow clock causes leakage current flow through the branches. Therefore, high-VTH and low-power (hvtlp type) transistors of the used 65 nm CMOS technology were utilized to suppress the leakage. The total power consumption of the comparator and latch is less than 10 nW.

Complete Modulator Circuit.

The overall modulator circuit is shown in Fig. 19. It employs a fourth-order loop filter implemented by single-loop full feedforward architecture. It has four integrators including an active one in the first stage and three passive ones in the following stages. The summation at the quantizer input is performed by using a SC network. A simple dynamic comparator is utilized as single-bit quantizer, while the power consuming preamplifier is removed in total.

Fig. 18. Dynamic comparator and SR latch

A basic resonator feedback composed of two switches and a small capacitor Cb is employed to optimize the NTF's zero location near the edge of signal bandwidth. A 5dB SNR improvement can be obtained according to the simulation. The commonmode voltage is set to the middle of the power supply, i.e. 0.35 V. The reference voltage is set to 0.5 V, which is defined by VREFP of 0.6 V and VREFN of 0.1 V.

The capacitor value of the first integrator (i.e., CS1) and the signal feedforward path (i.e., Cf0) are selected to fulfill the kT/C noise requirement of the modulator with a safe margin [START_REF] Wang | A 0.5 V Feedforward Delta-Sigma Modulator with Inverter-Based Integrator[END_REF]. The other modulator sampling and feedforward capacitors (i.e., CSi and Cfi for i = 2, 3, 4) are chosen to satisfy the modulator coefficients listed in Table 1. The first integrating capacitors (i.e., C1) is chosen to realize the coefficient a1 = 0.2, while the rest of the integrating capacitors (i.e., Ci for i = 2, 3, 4) are selected from the passive filter requirement, as discussed in section 3.2. It is worth to be pointed out that the first active stage suppresses the thermal noise or kT/C noise of the succeeding passive filters, thereby reducing the capacitor sizes drastically. Moreover, the resonator capacitor Cb is 0.25 pF in order to realize the resonator gain coefficient of 1/64. The capacitor values are summarized in Table 2.

Simulation Results

The proposed modulator was designed in a 65 nm CMOS technology and was simulated using a 256 kHz sampling clock frequency. voltage was set to 0.5 V (i.e., VREFP of 0.6 V and VREFN of 0.1 V), as shown in Fig. 19. The simulated output spectrum is shown in Fig. 20. Figure 21 shows the modulator peak SNDR with respect to the oversampling ratio (OSR). When the modulator is run at 1.0 MHz sampling frequency, the attained SNDR is 86 dB while dissipating 650 nW power. The input differential range is 1 VPP.

Compared to the previous passive modulator in [3], the clock frequency is halved by using higher-order filter, beneficial for power reduction in the ADC and the following decimating filter. Significant SNR improvement was achieved by cascading four integrators and also alleviating the low swing at the quantizer input with input feedforward architecture. It is important to point out that the total capacitor area is estimated to be scaled down by 50%, as compared to the fully passive modulator presented in [3]. The total sum of all capacitor values in the passive ADC in [3] and the proposed fourth-order active-passive modulator is 280 pF and 138 pF, respectively.

Comparison of the Power Efficiency

The performance of the presented modulator in section 3 is compared with previously reported modulators using passive filter(s) in The FOMW favors low-resolution ADCs, whereas the FOMS favors high-DR ADCs.

The passive modulator presented in [3] with 0.43 µW power consumption and medium resolution (68 dB SNR from a 0.7 V power supply) looks attractive when using FOMW definition, as given by equation [START_REF] Pun | A 0.5 V 74-dB SNDR 25-kHz Continuous-Time Delta-Sigma Modulator with a Return-to-Open DAC[END_REF]. When considering FOMS, the hybrid second-order and fourth-order modulators present the FOM of 156.5 and 175, respectively, which demonstrate high power-efficiency among the modulators [START_REF] Chen | A 0.25-mW Low-Pass Passive Sigma-Delta Modulator with Built-In Mixer for a 10-MHz IF Input[END_REF][3][START_REF] Chen | Design and Analysis of a CMOS Passive ΣΔ ADC for Low Power RF Transceivers[END_REF][START_REF] Yousry | A Third-Order 9-Bit 10-MHz CMOS ΔΣ Modulator with One Active Stage[END_REF][START_REF] Das | A 4 th -order 86dB CT ΔΣ ADC with Two Amplifiers in 90nm CMOS[END_REF]. In particular, the fourth-order modulator in [START_REF] Yeknami | A 0.7-V 400-nW Fourth-Order Active-Passive Delta-Sigma Modulator with One Active Stage[END_REF] employing a feedforward architecture presents an excellent energy-efficiency when both FOMW and FOMS are applied.

Summary

The ultimate purpose of this design was to improve the ADC resolution by solving some of the fundamental problems associated with the traditional passive modulators, discussed in section 2, such as extremely low voltage swing at the quantizer input and the comparator non-idealities including offset and noise. Furthermore, cascading three passive filters became possible by using feedforward modulator architecture. (e) Simulation results were provided in [START_REF] Yousry | A Third-Order 9-Bit 10-MHz CMOS ΔΣ Modulator with One Active Stage[END_REF][START_REF] Yeknami | A 0.7-V 400-nW Fourth-Order Active-Passive Delta-Sigma Modulator with One Active Stage[END_REF] Significant power reduction was obtained through (i) the reduced clock frequency by using a fourth-order and power-efficient loop filter, (ii) the removal of the power consuming preamplifier and (iii) the relaxed amplifier performance requirements in the full feedforward modulator structure.

The main advantage of the first active filter is that it can suppress the comparator nonidealities to a high extent. Additionally, due to the gain of this stage the thermal noise from the succeeding passive filters is also attenuated, resulting in significant capacitor area reduction.

Since in the feedforward architecture the loop filter mainly processes the quantization noise, the continual attenuation along with the passive integrator does not harm the signal components, another advantage of using passive stages in the feedforward structure. Therefore, three cascades of passive filters were exploited to create higherorder noise-shaping, which can decrease the OSR or sampling clock frequency leading to huge digital and analog power reduction. Furthermore, the input feedforward structure is suited well for low-power ΔΣ modulator design due to offering low integrators swing, which relaxes the slew rate requirement of the OTAs. Therefore, the slew rate and GBW of the OTA in the active stage were scaled down.

The impact of parasitics of the sampling and integrating capacitors on the performance of passive filter and the overall modulator was investigated and the simulation results were included.

Compared to the second-order passive modulator implemented in 65 nm technology [3] using distributed feedback architecture, the clock frequency in the proposed modulator reduced from 500 kHz to 256 kHz, which is beneficial for both analog performance scaling down and digital power reduction. The SNDR improved from 65 dB to 80 dB (2.5-bit resolution improvement), while the attained power of 400 nW is in the same order as the previous design (i.e., 430 nw). In other words, the powerefficiency (or FOM) of the overall modulator was enhanced from 296 fJ/step to 47 fJ/step, showing the effectiveness of combined feedforward structure and cascade of passive integrators. The attained FOM of 47 fJ/step makes this design a suitable candidate for low-voltage low-power ADC designs intended for medical applications.

Fig. 2 .

 2 Fig. 2. Passive lowpass filter in a single-ended form together with two-phase non-overlapping clocks [7] (Courtesy of IEEE)

Fig. 4 .

 4 Fig. 4. Noise sources in a single-loop second-order passive modulator [7] (Courtesy of IEEE)

Fig. 6 .

 6 Fig. 6. The NTF magnitude of the designed 4th-order modulator neglecting the resonator

Fig. 7 .

 7 Fig. 7. Integrators output swing in mV using a -1.94 dBFS, 187 Hz input signal. Comp represents the comparator input signal, and Inti (i = 1-4) represents the ith integrator output [7] (Courtesy of IEEE)

Fig. 8 .

 8 Fig. 8. (a) Simulated voltage swing at the quantizer input; (b) simulated SNDR across ρ. -1.94 dBFS, 187 Hz sinusoidal signal was applied in both cases [7] (Courtesy of IEEE)

Fig. 9 .Fig. 10 .

 910 Fig. 9. (a) The basic passive filter associated with lumped parasitic capacitor; (b) the simulated transfer function with/without parasitic capacitor [3] (Courtesy of IEEE)

Fig. 11 .

 11 Fig. 11. Simulated output spectra with/without local resonator using a -1.94 dBFS, 187-Hz input signal [7] (Courtesy of IEEE)

Fig. 12 .

 12 Fig. 12. (a) A 2 nd -order passive low-pass filter built from the cascade of two basic passive filters, (b) Equivalent model in sampling phase Ф1

7 Fig. 13 .

 713 Fig. 13. The proposed two-stage load-compensated amplifier employing body-driven gainenhancement technique; the bodies of p-MOS transistors are tied to the modulator commonmode voltage vcm = VDD/2. Sizes are given in µm unit

Fig. 14 .Fig. 15 .

 1415 Fig. 14. The simulated typical DC gain with/without gain-enhancement technique

Fig. 17 .

 17 Fig. 17. The STF magnitude of the designed 4th-order modulator

Fig. 19 .

 19 Fig. 19. Schematic of the proposed fourth-order active-passive modulator [7] (Courtesy of IEEE)

Fig. 20 . 5 Fig. 21 .

 20521 Fig. 20. Simulated modulator output spectrum with a -2.85 dBFS, 109 Hz input and 16384-points FFT [7] (Courtesy of IEEE)

( a )

 a FOMW = Power/(2 ENOB ×2×BW) known as the Walden FOM (b) FOMS = DR(dB)+10log (BW/Power) known as the Schreier FOM (c) DT-APSDM = Discrete-Time Active-Passive Delta-Sigma Modulator (d) CT-APSDM = Continuous-Time Active-Passive Delta-Sigma Modulator

Table 1 .

 1 It must be pointed out that the actual coefficients ai for i = 2, 3, 4 is 1/(1+ρ) which is included into the passive filter transfer function in Fig.5. The NTF can be calculated as

	(	)	4 4	91 . 7 03 . 2	3 3	97 . 5 76 . 11	2 2	19 . 15 42 . 13	64 . 4 69 . 4

Table 3

 3

	summarizes the simulation

Table 2 .

 2 Capacitor values in pF[START_REF] Yeknami | A 0.7-V 400-nW Fourth-Order Active-Passive Delta-Sigma Modulator with One Active Stage[END_REF] (Courtesy of IEEE)

Table 3 .

 3 Perfprmance

results

[START_REF] Yeknami | A 0.7-V 400-nW Fourth-Order Active-Passive Delta-Sigma Modulator with One Active Stage[END_REF]

(Courtesy of IEEE)

Table 4 .

 4 Two commonly used FOMs (Walden and Schreier FOMs) are defined below:

	FOM	W		2	(	Power 02 . 6 / ) 76 . 1  SNDR		2		BW	(15)
	FOM	S		DR dB		10	log(	BW	)	(16)
										Power

Table 4 .

 4 Performance comparison with previously reported modulators using passive filter

	Reference	Type	BW	Sampling	SNDR	DR	Power	FOMW a	FOMS b
			[Hz]	Rate[MHz]	[dB]	[dB]	[μW]	[pJ/step]
	[2] Chen	DT Passive	20k	10	67	78	250	3.41	157
	[4] Chen	DT Passive 100k	104	74.1	80.5	830	1.0	159.7
	[5]Yousry e	DT	10M	640	56	54	5500	0.55	146.6
		APDSM c
	[6] Das	CT	600k	256	N/A	86	5400	N/A	166.5
		APDSM d
	[3] Fazli	DT Passive	0.5k	0.5	65	65	0.43	0.3	144
	[3] Fazli	DT	0.5k	0.25	70	70.5	1.27	0.49	156.5
		APDSM
	[7] Fazli e	DT	0.5k	0.256	80.3	84	0.4	0.05	175
		APDSM


Kyprianos Papadimitriou

Sotiris Thomas
email: sthomas@mhl.tuc.gr

Apostolos Dollas
email: dollas@mhl.tuc.gr

An FPGA-Based Real-Time System for 3D Stereo Matching, Combining Absolute Differences and Census with Aggregation and Belief Propagation

Keywords: stereo matching, correspondence problem, real-time, field programmable gate arrays, absolute differences, census, belief propagation

The implementation of 3D stereo matching in real time is an important problem for many vision applications and algorithms. The current work, extending previous results by the same authors, presents in detail an architecture which combines the methods of Absolute Differences, Census, and Belief Propagation in an integrated architecture suitable for implementation with Field Programmable Gate Array (FPGA) logic. Emphasis on the present work is placed on the justification of dimensioning the system, as well as detailed design and testing information for a fully placed and routed design to process 87 frames per sec (fps) in 1920 × 1200 resolution, and a fully implemented design for 400 × 320 which runs up to 1570 fps.

Introduction

Stereo vision is a research area in which progress is made for some decades now, and yet emerging algorithms, technologies, and applications continue to drive research to new advancements. The purpose of stereo vision algorithms is to construct an accurate depth map out of two or more images of the same scene, taken under a slightly different angle/position. In a set of two images one image has the role of the reference image while the other is the non-reference one. The basic problem of finding pairs of pixels, one in the reference image and the other in the non-reference image that correspond to the same point in space, is known as the correspondence problem and has been studied for many decades [START_REF] Ballard | Computer Vision[END_REF]. The difference in coordinates of the corresponding pixels (or similar features in the two stereo images) is the disparity. Based on the disparity between corresponding pixels and on stereo camera parameters such as the distance between the two cameras and their focal length, one can extract the depth of the related point in space by triangulation. This problem has been widely researched by the computer vision community and appears not only in stereo vision but in other image processing topics as well such as optical flow calculation [START_REF] Marr | Vision[END_REF]. The range of applications of 3D stereo vision cannot be underestimated, with new fields of application emerging continuously, such as in recent research on shape reconstruction of space debris [START_REF] Di Carlo | A novel algorithm and hardware architecture for fast video-based shape reconstruction of space debris[END_REF].

The class of algorithms which we study falls into the broad category of producing dense stereo maps. An extensive taxonomy of dense stereo vision algorithms is available in [START_REF] Scharstein | A Taxonomy and Evaluation of Dense Two-Frame Stereo Correspondence Algorithms[END_REF], and an online constantly renewed comparison can be found in [5], containing mainly software implementations. In general, the algorithm searches for pixel matches in an area around the reference pixel in the non-reference frame. This entails a heavy processing task as for each pixel the 2D search space should be exhaustively explored. To reduce the search space, a constraint called epipolar line can be applied. This constraint aims at reducing the 2D area search space to a 1D line by assuming that the two cameras are placed on the same horizontal axis (much like the human eyes) and that the corresponding images do not have a vertical displacement, thus the pixels which correspond to the same image location are only displaced horizontally. The epipolar line constraint is enforced through a preprocessing step called rectification, which is applied to the input pair of stereo images. In this work we concentrate on the stereo correspondence algorithm and not on the rectification step, assuming that images are rectified prior to processing. We present an FPGA-based implementation that is scalable and can be adjusted to the application at hand, offering great speed-up over a software implementation. Essentially, we extend our work published in [START_REF] Thomas | Architecture and Implementation of Real-Time 3D Stereo Vision on a Xilinx FPGA[END_REF], by including more results and a detailed analysis on aspects related to performance and resource utilization. We should note here that stereo matching is embarrassingly parallel and thus someone would reasonably expect getting high performance gains from a custom hardware implementation. Hence, our contributions go beyond solely achieving high performance results, and these are:

an analysis showing how the use of aggregation alleviates the need to employ the more computationally demanding Sum of Absolute Differences (SAD) algorithm while still maintaining good results; an analysis on how to dimension the combination of the Absolute Diferences (AD) and the Census algorithms with aggregation in a single hardware implementation; the FPGA-based architecture with detailed tradeoff analysis in the use of its primitive resources (Block RAM, Flip-Flops, logic slices), which justifies the use of FPGAs in the field of stereo vision; a placed-and-routed design allowing real-time processing up to 87 fps for full HD 1920 × 1200 frames in a medium-size FPGA; a modification at the final phase of design cycle that improved by 1.6x the system performance; a detailed cost vs. accuracy analysis and on-FPGA RAM usage for design optimization.

The chapter is organized as follows: Section 2 discusses previous work, focusing mainly on hardware-related studies, and with a more up-to-date comparison of recent research results vs. those in our previous work [START_REF] Thomas | Architecture and Implementation of Real-Time 3D Stereo Vision on a Xilinx FPGA[END_REF]. Section 3 describes the algorithm and its individual steps. Section 4 analyses the benefits of mapping the algorithm to an FPGA with emphasis on dimensioning, and especially on the usefulness of aggregation in addition to AD and Census vs. the SAD algorithm. An in-depth discussion of our system is given in Section 5, including the implementation of belief propagation. Section 6 has the system performance and the usage of resources, and Section 7 summarizes the chapter.

Relevant Research

In recent years there is considerable work on 3D stereo vision, and in particular on hardware systems to support real-time 3D stereo vision. Most of these results are with FPGA technology, although there exist approaches with Digital Signal Processors (DSP) and Graphics Processor Units (GPU). Due to its intrinsic heavy parallelization and pipelining, it is one of the most promising candidates that can benefit from hardware implementation. However, several factors should be considered when it comes to develop such a design. The main factors are the maximum resolution supported and whether processing can be done at realtime; a rate of 30 fps is desirable for the human eye, but higher rates might be useful in industrial applications. Table 1 consolidates representative implementations in different technologies, with information on the maximum resolution and processing rate. The work in [START_REF] Konolige | Small Vision Systems: Hardware and Implementation[END_REF] was one of the earliest ones to combine the development of cost calculation with the Laplacian of Gaussian in a DSP. More recently, several works developed different algorithms in fully functional FPGA-based systems ranging from relatively simple [START_REF] Murphy | Low-Cost Stereo Vision on an FPGA[END_REF][START_REF] Hadjitheophanous | Towards Hardware Stereoscopic 3D Reconstruction, A Real-Time FPGA Computation of the Disparity Map[END_REF] to more complex ones [START_REF] Masrani | A Real-Time Large Disparity Range Stereo-System using FPGAs[END_REF][START_REF] Jin | FPGA Design and Implementation of a Real-Time Stereo Vision System[END_REF]15,[START_REF] Jin | Fast and Accurate Stereo Vision System on FPGA[END_REF]. The authors of [START_REF] Jin | FPGA Design and Implementation of a Real-Time Stereo Vision System[END_REF]15] have designed full stereo vision systems incorporating the rectification preprocessing step. The work in [START_REF] Humenberger | A Fast Stereo Matching Algorithm Suitable for Embedded Real-Time Systems[END_REF] provides designs of an algorithm based on census transform in three different technologies, i.e. CPU, GPU and DSP; the maximum performance was obtained with the GPU. The authors in [START_REF] Rhemann | Fast Cost-Volume Filtering for Visual Correspondence and Beyond[END_REF] introduced a local stereo matching scheme, making use of a guided filter for weighted cost aggregation to achieve impressive results relative to the quality of local algorithms. Their implementation on a GPU achieved real-time performance with 23 fps on average. The authors of [START_REF] Kalarot | Stereo Vision Algorithms for FPGAs[END_REF] compare FPGA and GPU implementations of stereo vision to expose the trade-off between the flexibility but relatively low speed of an FPGA, and the high speed and fixed architecture of the GPU; that work highlights the relative strengths and limitations of the two systems. An interesting work reviewing algorithms suitable for low-cost FPGA implementation was published in [START_REF] Mattoccia | Stereo Vision Algorithms for FPGAs[END_REF], concluding that the memory footprint of the algorithm is the most important consideration given the limited on-chip memory of FPGAs; three different algorithms were demonstrated as a part of a real-time self-contained stereo vision system based on a Xilinx Spartan 6.

The supported disparity is an important parameter that scales with the image resolution. As shown in Table 1, disparity for medium resolutions should be between 64 and 128; this was the case for our functional prototype as well.

Our system surpasses all previous systems in terms of performance. The system we implemented in a Xilinx Virtex-5 FPGA sustains a processing rate of 1570 fps for 400 × 320 frames. To the best of our knowledge this is far better than any published work. For 640 × 533 resolution we achieved a processing rate of 589 fps, while we support 1920 × 1200 resolution at a rate of 87 fps. Moreover, our analysis differs from other publications in the sense that we study the way FPGA primitive resources suit the characteristics of each stage of the stereo vision algorithm.

A more recent version of our system, aiming at a low-cost embeddable design has been published in [START_REF] Rematska | A Low-Cost Embedded Real-Time 3D Stereo Matching System for Surveillance Applications[END_REF]. This design is substantially smaller in FPGA resources vs. the current work, however, the design in [START_REF] Rematska | A Low-Cost Embedded Real-Time 3D Stereo Matching System for Surveillance Applications[END_REF] has fewer capabilities, including a 15% loss of 3D stereo matching capability in the near depth of field, which comes from limitations in the number of pixels among which the disparities are computed (54 in [START_REF] Rematska | A Low-Cost Embedded Real-Time 3D Stereo Matching System for Surveillance Applications[END_REF] vs. 64 in the present work), and the number of frames per second was deliberately lowered to 30 in order to reduce power consumption; however, with a higher clock rate a higher fps rate could be achieved.

The Algorithm

A typical approach in stereo matching is to employ a local algorithm which matches corresponding pixels in the image pair. This local algorithm computes matching costs between a pixel in the reference frame and a set of pixels in the target frame and selects the match with the minimum cost. This is known as the Winner-Take-All (WTA) strategy, according to which the algorithm selects the match with the global minimum cost in the search space. Essentially, this process is equivalent to computing a 3D cost matrix (called Disparity Search Image or DSI, shown in Figure 1) of size W × H × D max , -where W the frame width, H the frame height and D max the size of the search space -and selecting the index of the minimum in the D max dimension. To improve the results, usually a cost aggregation step that acts on the DSI is interjected between the cost computing and match selecting steps. Post-processing steps can further refine the resulting disparity map. Our algorithm consists of the cost computation step implemented by the Absolute Difference (AD) census combination matching cost, a simple fixed window aggregation scheme, a left/right consistency check and a scan-line belief propagation solution as a post processing step. Each step of the algorithm will be explained below, whereas the justification for the choice of this combination of algorithms will become evident from quantitative data in Section 4.

The AD measure is defined as the absolute difference between two pixels, C AD = |p 1 -p 2 |, while census [START_REF] Zabih | Non-parametric Local Transforms for Computing Visual Correspondence[END_REF] is a window based cost that assigns a bitstring to a pixel and is defined as the sum of the Hamming distance between the bit-strings of two pixels. Let W c be the size of the census window. A pixel's bit-string is of size W 2 c -1 and is constructed by assigning 1 if p i > p c or 0 otherwise, for p i ∈ W indow, and p c the central pixel of the window. The two costs are fused by a truncated normalized sum:

C(p R , p T ) = max( C AD (p R , p T ) C M ax AD + C Census (p R , p T ) C M ax Census , λ trunc ) (1)
where λ trunc is the truncation value given as parameter. This matching cost encompasses image local light structure (census) as well as information about the light itself (AD), and produces better results than its parts alone, as was shown in [START_REF] Mei | On Building an Accurate Stereo Matching System on Graphics Hardware[END_REF]. At object borders, the aggregation window necessarily includes costs belonging to two or more objects in the scene, whereas ideally we would like to aggregate only costs of one object. For this reason, truncating the costs to a maximum value helps at least limiting the effect of any outliers in each aggregation window [START_REF] Scharstein | A Taxonomy and Evaluation of Dense Two-Frame Stereo Correspondence Algorithms[END_REF].

After initializing the DSI volume with AD-Census costs, we perform a simple fixed window aggregation on the W × H slices of the DSI, illustrated in Figure 2. This is based on the assumption that neighbouring pixels (i.e. pixels belonging in the same window) most likely share the same disparity (depth) as well. Although this does not stand for object borders and slanted surfaces, it produces good results. On the other hand, one should select carefully the size of the aggregation window W a , as large windows tend to lead to an edge fattening effect in object borders while small aggregation windows lead to loss of accuracy in the inside area of an object itself, which results in a noisy output. Finally, we perform a left/right consistency check (LRC check) which repeats the match selection step but with the opposite frame as reference and compares the new disparity image with the original one. This process allows to detect mismatches due to occlusions (areas of the scene that appear only in one frame).

Using the mismatches detected, our scan-line belief propagation solution propagates local confident matches along the scan-line, by accumulating matches that passed the LRC check in a queue (called confident queue due to that it stores only disparities that passed the LRC check), and propagating them to local matches classified as occlusions in a neighborhood queue.

Dimensioning of the FPGA Architecture

The algorithm can be mapped on an FPGA very efficiently due to its intrinsic parallelism. For instance, the census transform requires W 2 c -1 comparisons per pixel to compute the bit-string. Aggregation also requires W 2 a additions per cost. For each pixel we must evaluate 64 possible matches by selecting the minimum cost. These operations can be done in parallel. The buffer architecture requires memories to be placed close to each other, as they shift data between them in a very regular way. FPGA memory primitives (BRAMs) are located in such a way they facilitate this operation. Figure 3 shows the critical components for the different steps of the algorithm. Our system shares the pixel clock of the cameras and processes the incoming pixels in a streaming fashion as long as the camera clock does not surpass the system's maximum frequency. This way we avoid building a full frame buffer; we instead keep only the part of the image that the algorithm is currently processing. It is important to assess the need for flexibility regarding the algorithm parameters, and the gains of such a setup. First and foremost, we are seeking to build a system that is frame-agnostic. Stating differently, we aim at supporting a series of frame sizes within a range of choices; we regard this feature as obligatory. However, a limit on the maximum frame width was imposed for reasons explained in Section 6. In addition, all the algorithmic parameters are adjustable; the maximum disparity search range D max , the census window size W c , and the aggregation window size W a . We chose to structure our system in a modular way in order to easily add/remove features. Features such as scanline belief propagation and aggregation can be turned on or off selectively by the user. Figure 4 shows performance results without aggregation and with various aggregation window sizes. In order to develop an efficient architecture it is important to understand how resources are used. In terms of sheer performance when no aggregation is used, the SAD algorithm is the best, and so it would seem that it is best to implement it in hardware. No aggregation means that the aggregation window is of size 1. , when computational cost is considered, the SAD algorithm is by far more expensive than the alternatives, as it has approximately 2 × W 2 comparisons. It is therefore useful to consider cost vs. performance when we introduce aggregation to the system, where we notice that the system-level performance with aggregation comes close to the SAD performance, but at a lower computational cost.

The next question to answer in the development of a useful architecture is the tradeoff between the census window size vs. the aggregation window size. The effects of different census window sizes and different aggregation window sizes is illustrated in Figure 5, which contains in a more clear form the information from Figure 4 for the algorithms which were actually implemented in our system. We analyzed the influence of the algorithm's parameters on the quality metric of percentage of good matches, over six (6) datasets of Middlebury's 2005 database [5]. We have settled on a W c = 9 × 9 sized census window, a W a = 5 × 5 sized aggregation window and a D max = 64 disparity search range; these values offer a good trade-off between overall quality and computational requirements. We followed a similar procedure to determine all the other secondary parameters as well, such as the confident neighborhood queue size and the neighborhood queue size of the scan-line belief propagation module, and the LR check threshold of the LR consistency check module [START_REF] Humenberger | A Fast Stereo Matching Algorithm Suitable for Embedded Real-Time Systems[END_REF].

There are negligible gains if we choose a larger W c or W a . The maximum achievable percentage of good matches was 78,36% for AD-Census (W c =7, W a =13), therefore there is no actual benefit by choosing a large aggregation window. It is thus our choice to fix the window sizes in our implementation. Our design remains generic in any parameter aspect but it is not reconfigurable at runtime. This decision simplifies our hardware design. For purposes of evaluation and experimental verification of the design we designed our system using Xilinx FPGAs, namely, a Virtex 5 XC5VLX110T as well as a Spartan 3 1000, setting the parameters accordingly to fit the FPGA device at hand.

Last but not least, we need to consider what happens with occluded pixels from one or the other camera. It is therefore useful to allow for some resources to be used for Belief Propagation (BP), as shown in Section 5. Belief propagation (which uses results from the Left-Right consistency check) does not consume significant resources but it solves the problem of uncertainty due to occluded pixels which would result if only one camera were used as the only reference image.

Design and Implementation

The system in Figure 6 receives two 8-bit pixel values per clock period, each one for the corresponding image in the stereo pair. A window buffer is constructed for each data flow in two steps. Lines Buffer stores W c -1 scan-lines of the image, each in a BRAM, conceptually transforming the single pixel input of our system to a W c sized column vector. Window Buffer acts as a W c sized buffer for this vector, essentially turning it into a W 2 c matrix. This matrix is subsequently fed into Census Bitstring Generator of Figure 6, which performs W 2 c -1 comparisons per clock, producing the census bit-string. Central pixels/Bit-strings FIFO stores 64 non-reference census bit-strings and window central pixels, which along with the reference bit-string and central pixel are driven to 64 Compute Cost modules. This component performs the XOR/summing that is required to produce the Hamming distance for the census part of the cost, along with the absolute difference for the AD part and the necessary normalization and addition of the two. The maximum census cost value is 80 as there are 81 pixels in the window excluding the central pixel from calculations. Likewise, the maximum AD cost value is 255 as each pixel is 8 bits wide. As the two have different ranges, we scale the census part from the 0-80 range to a 0-255 range, by turning it into an 8-bit value. To produce the final AD-Census cost we add the two parts together, resulting in a 9-bit cost to account for overflow. Truncating this cost to 6-bit produces a slight improvement in quality as discussed in Section 3, and also reduces buffering requirements in the aggregation step. For the aggregation stage, 22 line buffers (Aggregation Lines Buffer in Figure 6) are used for 64 streams of 6-bit costs, each lines buffer allocated to 3 streams. BRAM primitives are configured as multiples of 18K independent memories, so we maximize memory utilization by packing three costs per BRAM, accepting a maximum depth of 1024 per line. Like the Lines Buffers at the input, they conceptually transform the stream of data to W a sized vertical vectors. Each vector is summed separately in the Vertical Sum components and driven to delay adders (Horizontal Sum), which output X(t) + X(t -1) + ... + X(t -4). At the end of this procedure we have 64 aggregated costs.

Following the aggregation of costs, the LRC component illustrated in Figure 7, filters out mismatches caused by occlusions; its operation is illustrated in Figure 8. The architecture of LRC is based on the observation that by computing the right-to-left disparity at reference pixel p(x, y), we have already computed the costs needed to extract the left-to-right disparity at non-reference pixel p (x, y). The LRC buffer is a delay in the form of a ladder that outputs the appropriate left-to-right costs needed to extract the non-reference disparity. The WTA modules select the match with the best (lowest) cost using comparator trees. The reference disparity is delayed in order to allow enough time for the non-reference disparities space to build up in NonReference Disparities Buffer and then it is used to index said buffer. Finally, a threshold in the absolute difference between Disp RL (x, y) and Disp LR (x, y) indicates the false matches detected. Furthermore, at each cycle it calculates the average of the confident disparities, as this value will ultimately be propagated to non confident ones in the neighborhood queue. This average is calculated by a constant multiplier, using fixed point arithmetic and rounding to reduce any number representation errors. On the other hand, the Neighborhood Queue simply keeps track of local disparities and their LR status. When the Propagate signal is asserted (active when a new confident disparity is calculated and stored in the New Confident Disparity register), the NewDisp is written to all records with a false LRC flag. NewDisp is selected to be Previous Confident Disparity when this value is smaller than New Confident Disparity, otherwise it is assigned New Confident Disparity, effectively propagating confident background depths.

We report, below, some noticeable points regarding system operation:

-A small frame of unknown disparities is formed around the final disparity image, where due to the image boundaries, the windows cannot be formed and thus disparities cannot be computed. -Searching for matches near the image boundary leads to reduced or trivial disparity search spaces. In such cases our system finds the best match in the possible range. Left/Right Consistency check filters out any incorrect matches due to small search spaces. -Belief propagation is activated on each end of line regardless of the LRC indication, in order to fill in the occluded right area of the image. -In order for high resolutions to work acceptably, the user needs to either increase the D max accordingly or alternatively to reduce the inter-camera spacing. The second option is preferable as it has no computational consequences, whereas increasing D max has a cost on FPGA resources. Moreover, as the features of the images are now more spaced out in pixel distances, the other parameters of the system need also to be adjusted in order to maintain output quality.

The system which was described, above, can process one pixel pair per clock period, after an initial latency. The most computationally intensive part of the main stage of the algorithm lies in the XOR/sum module of the AD census, which computes the XOR/sum of 64 80-bit strings at the same time. A similar situation stands for the WTA module, which performs 64 11-bit simultaneous comparisons. We cope with both bottlenecks through fully pipelined adder/comparator trees in order to increase the throughput. After the initial implementation, we added extra pipeline stages to further enhance performance. Below we present the differences between the initial (unoptimized) design, and the second (optimized) design. Table 2 shows the performance results of the system implemented in a Xilinx Virtex-5 FPGA. The maximum clock after place and route for the unoptimized design is 131MHz, while for the optimized design is 201MHz. Table 3 has the differences in resource utilization between the two designs; it demonstrates that for a speed improvement of over 50%, the resource utilization penalty is rather small. Based on data we gathered from the tools, the critical path lies on a control signal driving the FSM of the aggregation line buffers; 16,6% is attributed to logic while the rest 83,4% of the delay is due to routing. We should point out here that W c , W a and D max parameters are related with tasks carried out in parallel, thus they do not affect system performance but only resource utilization. Table 4 has the distribution of resources along with the percentage breakdown in each type of resources for the optimized design. We conducted several experiments by varying the parameters in each stage so as to assess system performance in terms of scalability and increase in resource utilization. Tables 5,6, 7 have the FPGA resource results for different parameter values. It is obtained that the design clock is not affected. At the same time we observe that once a parameter increases, the amount of resources needed for a resource category might increase drastically while another category is not affected, i.e. in Table 6 as W c increases, the amount of flip-flops and LUTs increases as opposed to the amount of BRAMs which remains unchanged. Aggregation of the costs consumes most of our BRAM resources, as we have to construct D max ×W a cost line buffers (a total of D max ×W a ×F rameW idth× CostSize bits must be buffered). BRAM primitives of Virtex 5 FPGAs support only certain aspect ratios. The vendor tool employs these primitives to construct bigger memories, using an allocation algorithm. Memories with different widths/depths from those ratios are mapped to the closest possible solution but may not use the resources optimally. Memories with ratios of 1 × 16K (16,384 elements of 1-bit), 2 × 8K, 4 × 4K, 9 × 2K, 18 × 1K, 36 × 512 are guaranteed to utilize a single 18K primitive and thus use the resources optimally. In addition, very large frame sizes cause parameter bloating. In specific, images with 1800 × 1500 resolution require at least D max = 180 for achieving satisfactory results in terms of quality (without altering the current camera baseline). While keeping the other parameters constant (W c = 9, W a = 5), such a large D max would require buffering 180 × 5 × 1800 elements in the aggregation stage.

Due to the above we decided to put a limit on the image width. Restricting the frame width to 1024 pixels allowed us to:

-Pack at least two lines per 18K BRAM using a 18 × 1K BRAM primitive configuration. For each cost line we allocate 9 × 1024 bits. -Avoid excessive parameter bloating.

Using AD-Census, the costs are 9-bit long as described earlier. This benefits our design as BRAM primitives can be used optimally in a 18×1K configuration. Using pure Census, cost size is reduced to 7-bits. We can maximize BRAM usage by using 9-bit costs, so we have room to increase census window size W c up to 21 × 21, with little additional cost to resource usage.

If the cost size is less than 9-bits or if the frame width is less than 1024 we can pack more lines. This aspect of our design is also parametric, as depending on the frame size and cost size, each BRAM can fit up to 6 lines in a 36 × 512 BRAM configuration.

In an effort to reduce BRAM consumption even further, we performed a cost size-accuracy tradeoff experimental analysis, depicted in Figure 9. AD-Census was redefined as:

ADCensus = min(ADCensus, SaturationV alue) (2)
Selecting saturation values to be power of 2, can reduce cost size and thus fit more data into the BRAMs that implement the aggregation buffers. Our analysis shows that there is a slight benefit in doing so: for a saturation value of 63 (cost size reduced to 6-bits), and for the default W c and W a values of 9 and 5 respectively, we observe a 0.5% improvement over the cost without saturation. This is an important result because it puts our quality almost on par with a W c = 11 and W a = 5 parameter set. This slight improvement is attributed to the reduction of the influence of outliers within the aggregation window by truncating the cost. With 6-bit costs, we can pack 3 streams of costs per Aggregation Lines Buffer, thus reducing BRAM consumption even further. Note that all the results presented so far with regard to FPGA resource utilization, correspond to designs incorporating the previous optimizations.

Figure 10 shows the effect of optimizations on BRAM utilization for W c = 9, W a = 5, D max = 64 and a maximum frame width of 1024 pixels. Operating with small frame sizes allows for optimal algorithm performance.

We performed extensive verification of our designs Figure 11 has the set of images we used to test our prototype. We entered stereo images and we compared the software and the FPGA output over the ground truth. The SW version aimed to support the validation phase; we developed it in Matlab prior to the FPGA design. In terms of the physical setup for the verification, Figure 12 shows the methodology we followed to validate the FPGA system. The values of the pixels in the output of the FPGA processing were subtracted from the values of the pixels in the output of the SW, pixel-per-pixel so as to create an array holding their differences. We obtained that SW and HW produced similar results. The error lines are attributed to a slightly different selection policy in the WTA process of the LRC stage. In particular, when it comes to compare two equal cost values, our SW selects one cost value randomly, while our HW selects always the first one. This variation occurs early in the algorithmic flow, thus it is not only propagated but it is also amplified in the belief propagation module where local estimates of correct disparities are spread to incorrectly matched pixels along the scan-line. Finally, the errors at the borders that occur in both SW and HW outputs as compared with the ground truth, are due to the unavoidable occlusions at the image borders. The actual prototype in the Virtex-5 FPGA can process images of up to 400 × 320 resolution. We put our efforts on building a high-speed stereo matching design, rather than solving the I/O issue. Instead, at off-line time we send images into internal BRAMs through a serial protocol; once the entire image is stored in the BRAMs the design starts processing it. We used hardware means for measuring the time to complete the FPGA processing, and by performing experiments on different images -mainly from Middlebury database -we achieved a processing rate of 1570fps. To the best of our knowledge this outperforms any published FPGA-based system.

Input

Ground truth SW output HW output

Conclusions and Future Work

In this chapter we presented the architecture and implementation of a real time stereo matching algorithm in an FPGA, which utilizes efficiently the strengths of this device. We validated the system on a prototype, and we exceeded realtime requirements by a large margin for various parameter configurations. In the future we will place our efforts to more advanced aggregation schemes as they are the key to better quality disparity maps for local methods. Another point that would benefit from further research is the scan-line belief propagation method, which we plan to augment to two dimensions and thus eliminate its streaking artifacts. Also we plan to complete the stereo vision core algorithm with rectification and full camera integration.

Fig. 1 .

 1 Fig. 1. Disparity Search Image (DSI) volume

Fig. 2 .

 2 Fig. 2. Example of 3x3 fixed window aggregation of DSI costs

Fig. 4 .

 4 Fig. 4. Comparison of Census, AD and SAD performance with various aggregation window sizes

Fig. 5 .

 5 Fig. 5. Quality results in terms of the good matches for different census and aggregation window sizes, when using the AD-Census

Fig. 6 .

 6 Fig. 6. Datapath of the cost computation (left side) and aggregation (right side)

Fig. 7 .

 7 Fig. 7. Datapaths of the left/right consistency check(left side) and scan-line belief propagation(right side)

Fig. 8 .

 8 Fig. 8. Top row has pixels of the Right image, whereas bottom row has pixels of the Left image. The grey pixel in the center of the Right image has a search space in the Left image shown with the broad grey area. To determine the validity of DispRL(x, y), we need all left-to-right disparities in the broad grey area, thus we need right-to-left costs up to x + Dmax. The same stands for the diagonal shaded pixel in the center of the Left image.

Fig. 9 .

 9 Fig. 9. Cost size/accuracy analysis. The peak value shifts to the right as the true maximum cost increases.

Fig. 10 .

 10 Fig. 10. BRAM resource utilization with the optimized aggregation buffer structure

Fig. 11 .

 11 Fig. 11. Top row has Moebius 400 × 320 input dataset from Middlebury database and the ideal (ground truth) result. The bottow row has algorithm's output from SW and HW implementations.

Fig. 12 .

 12 Fig. 12. Validation methodology

Table 1 .

 1 Implementation of 3D Stereo Vision in different technologies

	Ref Resolution Disparity fps Technology Year
	[7] 160 × 120	32	30	DSP	1997
	[8] 320 × 240	20	150 Spartan-3 2007
	[9] 320 × 240	16	75	Virtex-II 2010
	[10] 320 × 240	16	574	GPU	2010
	[6] 400 × 320	64	1570	Virtex-5 2013
	[11] 640 × 480	128	30 4 Stratix S80 2006
	[12] 640 × 480	64	230	Virtex-4 2010
	[13] 640 × 480	54	>30 Spartan-6 2013
	[14] 640 × 480	60	507.9 Virtex-6 2014
	[14] 1024 × 768	60	199.3 Virtex-6 2014
	[15] 1920 × 1080	300	30	Spartan-6 2011
	[6] 1920 × 1200	64	87	Virtex-5 2013

Table 2 .

 2 Design clock and processing rates for the optimized vs. unoptimized design in Virtex XC5VLX110T FPGA for various resolutions

	100x83 384x320 644x533 1024x853 1600x1333 1920x1200
	Unoptimized design (131MHz) 15,783fps 1,066fps 384fps 150fps	61fps	56fps
	Optimized design (201MHz) 24,216fps 1,635fps 589fps 230fps	94fps	87fps

Table 3 .

 3 Resource utilization of the unoptimized vs. optimized design in Virtex XC5VLX110T FPGA for Dmax = 64, Wc = 9, Wa = 5

		Slices (%)	LUTs (%) Flip-Flops (%) BRAMs (%)
	Available	17,280	69,120	69,120	148
	Unoptimized design (131MHz) 13,556 (78%) 37.107 (53%) 39,565 (57%)	59 (39%)
	Optimized design (201MHz) 14,239 (82%) 37,986 (55%) 41,792 (60%)	59 (39%)

Table 4 .

 4 Resource utilization of the optimized design in Virtex XC5VLX110T FPGA for Dmax = 64, Wc = 9, Wa = 5

		LUTs (%)	Flip-Flops (%) BRAMs (%)
	Available	69,120	69,120	148
	Total consumed	37,986/69,120 (55%) 41,792/69,120 (60%) 59/148 (40%)
	AD Census	25,135/37,986 (66%) 29,167/41,792 (70%) 8/59 (14%)
	Aggregation	6,547/37,986 (17%) 7,312/41,792 (17%) 51/59 (86%)
	Left/Right Check	4,638/37,986 (12%) 4,734/41,792 (11%)	0/59 (0%)
	Scanline Belief Propagation 543/37,986 (1.5%) 634/41,792 (1.5%)	0/59 (0%)

Table 5 .

 5 Impact of Dmax on resource utilization and performance, when Wc = 9 and Wa = 5

	Dmax	LUTs(%) Flip-Flops(%) BRAMs(%) Max Clock
	16	10,284(14%) 12,531(18%)	30(20%) 201.207MHz
	32	19,148(27%) 22,687(32%)	30(20%) 201.045MHz
	64	37,986(54%) 41,792(60%)	59(39%) 201.518MHz

Table 6 .

 6 Impact of Wc on resource utilization and performance, when Dmax = 64 and

	Wa = 5
	Wc	LUTs(%) Flip-Flops(%) BRAMs(%) Max Clock
	5 21,637(31%) 21,866(31%)	59(39%) 201.086MHz
	7 29,813(43%) 31,840(46%)	59(39%) 201.113MHz
	9 37,986(54%) 41,792(60%)	59(39%) 201.518MHz

Table 7 .

 7 Impact of Wa on resource utilization and performance, when Dmax = 64 and Wc = 9

	Wa	LUTs(%) Flip-Flops(%) BRAMs(%) Max Clock
	1 (off) 28,505(41%) 33,047(47%)	9(6%) 201.005MHz
	3	34,618(50%) 38,660(55%)	31(20%) 201.167MHz
	5	37,986(54%) 41,792(60%)	59(39%) 201.518MHz