Anvesha Amaravati

Manan Chugh

Arijit Raychowdhury

A SAR Pipeline ADC Embedding Time Interleaved DAC Sharing for Ultra-Low Power Camera Front Ends

The growing need for ultra-low power cameras for sensors, surveillance and consumer applications has resulted in significant advances in compressed domain data acquisition from pixel arrays. In this journal we present a novel 64-input Successive Approximation (SAR) Pipeline analog-to-digital converter (ADC) suitable for compressed domain data acquisition in camera front-ends. The proposed architecture features a time interleaved capacitive digital-to-analog converter (DAC) shared between column parallel ADCs for area savings (2.28X); and a shared amplifier stage for power savings (60%), achieving 4X throughput as compared to traditional architectures. Simulations on a 130nm foundry process shows that the proposed SAR Pipeline ADC draws 31µW at 2MS/s having a target Figure-of-Merit (FOM) of 87fJ/conv. per step at Nyquist rate. The proposed compressive sensing front end achieves per patch energy per patch of 0.9nJ.

Introduction

Mobile devices for IOT (Internet of Things) require CMOS image sensor (CIS) with low power and area [START_REF] Choi | A 45.5µW 15fps Always-On CMOS image sensor for Mobile and Wearable Devices[END_REF]. Traditional CIS for wearable devices consume power more than 50mW [START_REF] Deguchi | A 187.5Vrms-Read-Noise 51mW 1.4Mpixel CMOS Image Sensor with PMOSCAP Column CDS and 10b Self-Differential Offset[END_REF].In a CMOS image sensor system the most power consuming blocks are: digital image processing back end & column parallel ADCs [START_REF] Park | A high-speed low-noise CMOS image sensor with 13-b column-parallel single-ended cyclic ADCs[END_REF] [START_REF] Watabe | A 33 mpixel 120 fps cmos image sensor using 12 b column-parallel pipelined cyclic adcs[END_REF]. In most of the reported image sensors, column parallel ADCs draw 50-65% of the power of the entire image sensor signal acquisition chip [START_REF] Oike | CMOS Image Sensor With Per-Column ADC and Programmable Compressed Sensing[END_REF] [START_REF] Choi | A 45.5µW 15fps Always-On CMOS image sensor for Mobile and Wearable Devices[END_REF]. The power consumed by column parallel ADCs is proportional to the number of measurements to be performed by the ADC. It increases with the number of pixels. For next generation IoT devices like "always on" Camera based image sensors, human machine interface systems with built in machine intelligence, low power is the key enabler.

Fig. 1 shows the traditional nyquist domain signal processing. Pixel voltages are digitized using high speed column parallel ADCs. Digitized image is encoded using algorithms like discrete cosine transform (DCT), discrete wavelet transform (DWT) etc. The power budget for transmitter blocks is shown in in Fig. 2. We can observe that encoding part like DCT, DWT consumes significant amount of power followed by Analog to Digital signal acquisition etc. As the resolution of the image goes up the number of measurements per ADC goes up and hence the encoding power also increases. This places huge power constraint on acquisition device and transmitter.

Pixel

Array ADC DCT, DWT, etc..

Quantization

Modulator +PA Recently developed algorithms of compressive sensing (CS) promise to reduce the number of measurements with non-linear recovery at the back-end [START_REF] Donoho | Compressed sensing IEEE Trans[END_REF]. The signal processing chain for compressing sensing is shown in Fig. 3. This approach makes the encoding done at the transmitter simpler by completely eliminating power hungry blocks like DCT, DWT. If the pixel values in a camera are represented as a discrete time signal

X = [x 1 x 2 x 3 x 4 • • • x n ]
T , the number of measurements needed in traditional column parallel ADCs will be equal to n. Instead of n samples, CS needs only m linear measurements (m << n). Fig. 4 shows the plot of PSNR of the recovered image w.r.to number of measurements done at receiver. We can observe that to achieve PSNR of 30dB, 250 measurements are sufficient. PSNR of 30dB is sufficient for classifying objects [START_REF] Lee | Factorization for Analog-to-Digital Matrix Multiplication Report[END_REF]. Therefore the value of m can be as small as n/250. Therefore compressive sensing achieves significant reduction is encoding power & transmission bandwidth. The CS measurement matrix is given by Eq. 1. Here Y [m] is the m-dimensional measured array, φ is a random binary matrix of size m * n and follows the "Independent and Identically Distributed (IID)" property. X is traditionally recovered at the back-end using an optimization algorithm, like determining the L 1 norm [START_REF] Donoho | Compressed sensing IEEE Trans[END_REF].

Y [m] = φ[m, n] × X[n] =      0 1 • • • 1 1 1 • • • 0 . . . . . . . . . . . . 1 0 • • • 0 m,n      ×      x 1 x 2 . . . x n      (
In this paper we present a novel pipeline-SAR ADC architecture with capacitive DAC sharing with the capability of acquiring linear combinations of 64 pixel data in a single conversion cycle. This is suitable for such compressed domain data acquisition.

ADC Architectures for CS Image Acquisition

In prior work for obtaining compressed domain data, both analog and digital techniques have been used to perform compressive measurements from the raw data. Typically, analog implementations of compressed sensing require an analog to digital converter to improve accuracy & digital transmission [START_REF] Gruev | Implementation of Steerable Spatiotemporal Image Filters on the Focal Plane IEEE TCAS-II[END_REF] [START_REF] Robucci | Compressive sensing on a CMOS separable-transform image sensor[END_REF]. Resistor based compressed sensing multiplexor reported in [START_REF] Slavinsky | The Compressive Multiplexer for Multi-Channel Compressive Sensing[END_REF], suffers from static power dissipation and the number of inputs (n) is limited, making it suitable for RF receiver applications only. To overcome some of the disadvantages of analog CS circuits, [START_REF] Chen | Design and Analysis of a Hardware-Efficient Compressed Sensing Architecture for Data Compression in Wireless Sensors[END_REF] has proposed compression in the digital domain after Analog to Digital Conversion. Fig. 5. a) shows the technique proposed in [START_REF] Chen | Design and Analysis of a Hardware-Efficient Compressed Sensing Architecture for Data Compression in Wireless Sensors[END_REF]. The entire analog signal is converted into the digital domain by high-speed ADCs and the CS encoder does compression in the digital domain. This is primarily suited for low bandwidth application like bio-medical signal processing. However, for CIS of a typical 256 * 256 size, ADCs would need to acquire all the samples and then convert to the digital domain. The number of measurements by the ADC will not be reduced and it defeats the purpose of compressed domain data acquisition. Therefore ADC power will remain the same for image acquisition. Further, the size of digital CS encoder grows exponentially with the number of inputs. CS encoders will further add significant power along with the ADC making it infeasible for "always on" imaging front-end applications.

[i].Φ[i] RST Y[i] Φ[i] X[i]

CS MUX

Fig. 6. Simultaneous compression and quantization within [START_REF] Oike | CMOS Image Sensor With Per-Column ADC and Programmable Compressed Sensing[END_REF] To overcome the limitations of data acquisition followed by compressed domain measurements, Oike et.al, has proposed a CS camera through simultaneous averaging and quantization of pixels using a Σ -∆ ADC [START_REF] Oike | CMOS Image Sensor With Per-Column ADC and Programmable Compressed Sensing[END_REF]. Fig. 5. b) shows the schematic of the resetting Σ -∆ ADC used for such linear measurements. Pixel values are multiplied with random numbers (from the φ matrix) sequentially and passed to the input of the Σ -∆ ADC. This approach requires m measurements; however it requires n conversion cycles for one measurement. This architecture requires a 16 * 16 block for linear measurement. For each measurement of the block, the resetting Σ -∆ ADC needs 256 clock cycles. For m measurements Σ -∆ ADC needs n*256 clock cycles. During this conversion period, all the high gain amplifiers will remain on and consume power. Hence, for lowering the total power dissipation, faster conversion with the opportunity for power gating once the conversion is complete, will be critical.

Once compressed domain data is acquired, the image is often used for online classification to detect potential trigger signals. For such in-situ classification [START_REF] Zhang | A matrix-multiplying ADC implementing a machine-learning classifier directly with data conversion[END_REF] and trigger identification, 8bits of inputs are sufficient. We have plotted classification accuracy vs Bit resolution for MNIST data base in Fig. 7. We can observe that recognition accuracy becomes constant after more than 6 bits of resolution. Further, it has been shown that for most of the machine learning applications moderate resolution (6-8bits) is sufficient [1][11]. Fig. 8 shows the Energy per conversion with respect to the Signal to Noise and Distortion ratio (SNDR) for state of the art SAR, Pipeline and Σ -∆ ADCs. SNDR is related to effective number of bits (EN OB = SN DR -1.76/6) [START_REF] Gustavsson | CMOS Data converters for communication[END_REF]. From this plot we can observe that SAR ADC has best FOM (order of 10 -1000f J/conv) for moderate resolution (6-8 bits). Pipeline ADCs also have competitive FOM for moderate and high speed applications. Since most of the image sensors speed varies from 1MS/s to 10MS/s and we are interested in 8b of resolution for in-situ image processing applications, we propose a SAR-Pipeline ADC which achieves ultra-low power and high area efficiency. For most of the low power applications SAR ADCs are used since they consume ultra-low energy per conversion(Fig. 8). However, for portable image front-end applications resolution more than 4-5 bits SAR ADC occupies huge area since Fig. 8. Energy vs SNDR for state of the art reported SAR, Pipeline and Σ -∆ ADCs [START_REF] Murmann | ADC Performance Survey 1997-2015[END_REF] the MSB capacitance grows as 2 N . Since there will be many column parallel ADCs each will have capacitance of 2 N . To alleviate this problem two-stage SAR Pipeline ADCs are proposed [START_REF] Lee | A SAR-Assisted Two-Stage Pipeline ADC IEEE JSSC[END_REF] [START_REF] Zhu | A 50-fJ 10-b 160-MS/s Pipelined-SAR ADC Decoupled Flip-Around MDAC and Self-Embedded Off[END_REF]. SAR-Pipeline uses two stage SAR-ADC and an amplifier which is used for amplifying residue generated by stage 1 SAR ADC (Fig. 9). Both the SAR ADC stages operates in parallel and each stage has to resolve lesser number of bits (lesser DAC settling time & capacitance (hence lesser area) as compared to traditional SAR). Therefore, SAR-Pipeline ADCs can operate at much higher speeds with high area efficiency [START_REF] Zhu | A 50-fJ 10-b 160-MS/s Pipelined-SAR ADC Decoupled Flip-Around MDAC and Self-Embedded Off[END_REF]. One of the inherent advantage of SAR-Pipeline is residue voltage of Stag-1 SAR ADC is generated within its DAC after conversion phase. Hence this avoids extra DAC and clock phase to generate residue of Stage-1 unlike in traditional flash based Pipelined ADCs [START_REF] Zhu | A 50-fJ 10-b 160-MS/s Pipelined-SAR ADC Decoupled Flip-Around MDAC and Self-Embedded Off[END_REF]. Fig. 10 shows a previously reported multi-input SAR ADC used for compressed sensing (with 8 bit resolution). It uses charge sharing. The MSB capacitor is equally divided among the inputs. Because of charge sharing the inputs will get averaged after the sampling cycle. [START_REF] Guo | A Single SAR ADC Converting Multi-Channel Sparse Signals Proc[END_REF] demonstrates a 4 input CS SAR ADC for wireless applications. This technique requires (2 8 + 2 4 = 272C) number of capacitors for an 8 bit ADC and measures 256 inputs ( C is the unit capacitor). One of the main limitations of the proposed SAR ADC architecture for portable imaging application is the area occupied by the sampling capacitors [START_REF] Chen | A 64 fJ/step 9-bit SAR ADC Array With Forward Error Correction and Mixed-Signal CDS for CMOS Image Sensors IEEE TCASI[END_REF]. Dividing the MSB capacitors to accommodate 256 inputs requires 256 switches. For portable applications limited supply ≈ 1 -1.3V provides high R ON . This provides us the time constant (τ conv ) for conversion (min. sized capacitor of 50fF) of ≈ 220nsecs (DAC settling time). This allows a maximum sampling frequency of 730KHz. Hence, for high speed cameras (with 30frames/sec) the proposed ADC architecture will not be able to meet latency requirements. Further, [START_REF] Guo | A Single SAR ADC Converting Multi-Channel Sparse Signals Proc[END_REF] uses calibration for capacitor mismatch, a requirement for more than 6-bits of resolution. Fig. 11 is the proposed SAR-Pipeline with DAC sharing. We use 4 bit ADC as the first stage. Since 4-bit ADC has 16C capacitors, all the capacitors are divided into equal value of C and 16 inputs are applied. We have 3 instances of the same DAC which is used for accessing additional 48 inputs. Sampling is done in two phases. During sampling phase (S1) all 4 DAC's sample 16 inputs each. During second phase of sampling charge is redistributed between them. The averaged voltages across 4 DAC's during S1 phase given by Eq. 2.

V dac1 = (v 1 + v 2 + .... + v 16 ) 16 . . . V dac4 = (v 48 + v 2 + .... + v 64 ) 16 (2)
During the second sampling phase S2, averaging of V dac1 to V dac4 takes place. Therefore, the final voltage across DAC is given by Eq. 3.

V dacf = (V dac1 + .... + V dac4 ) 4 V dacf = (v 1 + .... + v 64 ) 64 V dacf = (X[0].φ[0] + .... + X[63].φ[63]) 64 (3)
We can observe form Eq. 3 that the final accumulated output represents the dot-product of the input pixel vector X with the sampling matrix, φ . φ can be random or programmed so that both random as well as structured compressed measurements can be obtained. As soon as S2 is done 3 DAC's are shared with neighboring column parallel ADC. Once the conversion in 4-bit SAR ADC is complete, we amplify the residue by 4x and pass it to a 5-bit fine ADC to resolve the LSBs. Ideally a gain of 16 is required for residue amplification. We use 1-bit digital redundancy in Stage 1 and half reference scaling for Stage 2 to reduce the gain requirement which helps to reduce the power in the high-gain op-amp [START_REF] Lee | A SAR-Assisted Two-Stage Pipeline ADC IEEE JSSC[END_REF].

Since all the capacitors we use are identical and of value C, calibration is not required (more details in section III). As 3 DAC's are shared with 4 ADC's, we need an additional capacitance of 12C. With 12C extra capacitance we can acquire linear measurements of 64 inputs in each conversion cycle. This DAC shared method significantly improves area efficiency and enables simultaneous acquisition of multiple inputs. In this architecture, the conversion time-constant (τ conv ) is determined by the 4-bit ADC settling time even tough we are sampling 64-inputs. This makes the architecture suitable for high speed sensing with large number of inputs. During this period we share 3 DACs with 3 of the neighboring ADCs. S3 to S8 are sampling phases of ADC2 to ADC4. S3 to S8 phase operates during conversion period of ADC1. Pipelining facilitates overlapping of Stage-1 and Stage-2 conversion phases. 1-bit redundancy is added in the first stage to accommodate capacitor mismatch and offsets of the comparator, amplifiers [START_REF] Lee | A SAR-Assisted Two-Stage Pipeline ADC IEEE JSSC[END_REF]. We also share residue amplifier between two neighboring ADCs to reduce the total power [START_REF] Zhu | A 50-fJ 10-b 160-MS/s Pipelined-SAR ADC Decoupled Flip-Around MDAC and Self-Embedded Off[END_REF]. Accumulator (10 bit) used to average 4 consecutive ADC output samples. The accumulator is reset after every 4 sampling cycles (F s ). The sampler operating at quarter sampling rate is used to capture the averaged output. The averaged output contains random measurement of 256 inputs. Fig. 12 also shows the control logic used for proposed CS front-end ADC architecture. Global reset (RST) is used generate S1, S2 and conversion phase for ADC1. S2 phase of ADC1 is used to trigger sampling phase for neighboring column parallel ADC. This process is continued for all 4 ADCs. Falling edge of S2 phase triggers the conversion phase of individual ADCs.

Vres

Design Components

In this section, the design details of the first and the second state of the ADC are discussed. The Op-amp open loop gain (A OL ), unity gain frequency (f u ) and swing (V p -p) target based on the inter-stage gain is given in Table . 1. The required values are derived as per gain error, gain bandwidth (GBW) requirement of the OTA to be within 1/2LSB of the ADC error [START_REF] Zhu | A 50-fJ 10-b 160-MS/s Pipelined-SAR ADC Decoupled Flip-Around MDAC and Self-Embedded Off[END_REF]. The worst case values across process corners is mentioned in the Simulated values of the Table . We can observe that, simulated values across process corners for gain, bandwidth are by a factor of two larger than required values. Fig. 15 shows the telescopic cascode OTA used as interstate amplifier. It is well suited for two stage pipeline SAR since the swing requirement is low and it has high gain bandwidth efficiency.

Stage 1 ADC and residue amplification

We use pre-amplifier with output offset compensation to limit the offset of Stage 1 SAR ADC. The residual offset (V os,res ) is given by Eq. 4.

Systematic variations has no effect of capacitor matching since all the capacitance in Stage 1 SAR ADC are equal to C. The capacitance mismatch standard deviation for metal-insulator-metal (MiM) is given by Eq. 5.

σ ∆C/C = A ∆C/C √ W L (5)
where A ∆C/C is process constant which is 1%.µ m for 0.13µm CMOS process [START_REF] Diaz | CMOS technology for MS/RF SoC[END_REF]. W &/ L are width and length of the capacitor. The minimum size allowed in 0.13µm is 5µm * 5µm. With minimum sized capacitor σ ∆C/C obtained will be 0.002.

As per [START_REF] Lin | Modeling of capacitor array mismatch effect in embedded CMOS CR SAR ADC[END_REF] maximum allowable capacitor mismatch for a resolution of n is given by Eq. 6.

∆C C max = 2 n 2 2n -2 n + 1 (6)
For n=9, ∆C/C max reaches close to 0.002. This shows the residue generated by first ADC will fall within the range of 1/8LSB of error. Hence the proposed architecture is robust towards capacitor mismatch.

Simulation Results

Performance of the proposed SAR-Pipelined ADC is verified through design and simulations in the 0.13µm Mixed-Mode CMOS. Fig. 17 shows the normalized output frequency spectrum of the proposed ADC for input frequency (F in ) of 248.34kHz at sampling rate (Fs) of 1MSPS. A 1024-point FFT shows SNDR of 49.5dB which is equivalent to an ENOB of 7.9. Fig. 18 shows the 64 inputs applied to ADC at each sampling cycle. Each 64 inputs corresponds to CS multiplexor output (Product of input vector with random number). Fig. 19 shows the ADC and accumulator outputs at each conversion cycles. For a particular case study, as shown in the figure, an ideal averaging without quantization results in a output of 270.11mV. The proposed ADC after accumulated 4 samples each provides an output of 269.53mV which is less than 1LSB of error.

Fig. 20 shows the SNDR of the proposed ADC from input frequency range of 0.2MHz to to 0.98MHz. The ENOB at Nyquist frequency is 7.56. This ENOB achieves Walden FOM [START_REF] Gustavsson | CMOS Data converters for communication[END_REF] of 85fJ/conv. step. The power budget for the proposed ADC is given in The energy per patch is given by Eq. 7.

Energy P atch = P * N c F s [START_REF] Gruev | Implementation of Steerable Spatiotemporal Image Filters on the Focal Plane IEEE TCAS-II[END_REF] where, P is the power drawn by ADC for each conversion, N c is the number of conversion cycles & F s is the sampling frequency. The energy per patch for the proposed design is 0.9nJ. Multiple techniques are proposed to achieve high throughput in column parallel ADCs used for image sensors. Time interleaved sharing DAC technique reduces the number of measurement required by a factor of 4. Sharing the amplifier between neighboring column parallel ADCs reduces the power by 64%. The proposed architecture can be used for wearable devices with ultra-low power requirements. Our design and simulation results show 87f J/conv. step with an average power of 31µW.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Traditional nyquist signal acquisition and transmission

Fig. 3 .

 3 Fig. 3. Compressed domain signal acquisition & transmission

Fig. 4 .

 4 Fig. 4. Recovered image using L1 norm

Fig. 5 .

 5 Fig.5. CS encoder on acquired samples of ADC[START_REF] Chen | Design and Analysis of a Hardware-Efficient Compressed Sensing Architecture for Data Compression in Wireless Sensors[END_REF]

Fig. 7 .

 7 Fig. 7. Classification accuracy vs Bit resolution for MNIST database

Fig. 9 Fig. 9 .

 99 Fig. 9. Proposed CS front-end architecture for CIS

Fig. 10 .

 10 Fig.10. Reported multi-input SAR-ADC[START_REF] Guo | A Single SAR ADC Converting Multi-Channel Sparse Signals Proc[END_REF]

Fig. 11 .

 11 Fig. 11. Proposed multi-input DAC sharing SAR ADC

Fig. 12 .Fig. 13 .

 1213 Fig. 12. Proposed SAR ADC with time-interleaved DAC sharing

Fig. 14 Fig. 14 .

 1414 Fig. 14 shows the Stage 1 of the proposed SAR-Pipeline ADC. 64 inputs are acquired from S1 and S2. Residue is fed into an amplifier with gain of 4. Stage

Fig. 17 .

 17 Fig. 17. Frequency spectrum of the proposed ADC (Fin=248.34kHz & Fs=2MHz)

Fig. 21

 21 Fig.18shows the 64 inputs applied to ADC at each sampling cycle. Each 64 inputs corresponds to CS multiplexor output (Product of input vector with random number). Fig.19shows the ADC and accumulator outputs at each conversion cycles. For a particular case study, as shown in the figure, an ideal averaging without quantization results in a output of 270.11mV. The proposed ADC after accumulated 4 samples each provides an output of 269.53mV which is less than 1LSB of error.Fig.20shows the SNDR of the proposed ADC from input frequency range of 0.2MHz to to 0.98MHz. The ENOB at Nyquist frequency is 7.56. This ENOB achieves Walden FOM[START_REF] Gustavsson | CMOS Data converters for communication[END_REF] of 85fJ/conv. step. Fig. 21 shows the DNL and INL of the proposed ADC across 256 digital codes. The worst case DNL is within 0.4LSB. INL is within 1LSB across all digital codes.

Fig. 18 .Fig. 19 .

 1819 Fig. 18. 64 inputs for ADC for every 1 sampling cycle

Fig. 20 .Fig. 21 .

 2021 Fig. 20. Simulation result of SNDR vs Input frequency at Fs=2MHz

  Even though the total power consumed from the supply is 50µW, since the amplifier is shared between two ADC, the power for individual ADC's is 31µW. The number of conversion cycles required for 16 * 16 patch size with compression ratio of 16 is (16 * 16 * 16)/64 = 64.

Table .2. The power number is w.r.to patch size of 16*16 and a compression ration (CR) of 16.

Table 2 .

 2 Power and capacitance contribution from individual blocks 8 Comparison with Reported WorksTable. 3 shows the comparison of the proposed design with state of the art CS architecture. Proposed design is scalable and can handle a large number of inputs at the same time. Due to parallelism achieved by sharing DACs between columns parallel ADCs high energy efficiency per patch is achieved.

		Block	Power/ Capacitance
	SAR Stage1 7µW	28C
	Amplifier 41µW	4C
	SAR Stage1 2.5µW	10C
	Accumulator 0.5µW	Nil
		Oike [5] Guo [17] Chen [10] This work
	ADC type	Σ -∆	SAR	SAR SAR-Pipeline
	Technology	0.15µm 0.13µm 0.09µm	0.13µm
	Design	Measured Simulated Measured Simulated
	No. of inputs	1	4	1	64
	Sampling cycles	256	1	256	4
	Fs	1MHz	1MHz	2kHz	2MHz
	Capacitance	NA	272C	256C	40C
	Power	NA	50µW	5µW	31µW
	Energy/Patch	NA	51nJ	640nJ	0.9nJ

Table 3 .

 3 Comparison with reported works

where V os,pre-amp and V os,latch are the pre-amplifier offset and latch offset respectively. A p is the pre-amplifier gain. The 3σ V os,pre-amp and V os,latch are 5mV and 30mV respectively. The gain amplifier features a cross coupled load which provides a high gain of 15. The residual offset is 2.33mV which is 0.25LSB of the sub-ADC.

We use telescopic cascoded OTA in the proposed design for residue amplification. Telescopic cascoded OTA has high power efficiency for a given gain bandwidth (GBW) [START_REF] Gustavsson | CMOS Data converters for communication[END_REF]. Because of half gain and half reference implementation of the ADC, the open loop gain of the OTA is reduced. The OTA achieves a swing of 300mV p-p .

Stage 2 ADC

Fig. 16 shows the Stage 2 of the proposed SAR-Pipeline ADC. We use a split capacitor architecture to reduce the area and power for the second ADC. Since the non-linearity of this ADC will get divided by the gain of the amplifier, it can be neglected. For the comparator in stage 2 of the proposed ADC, a pre-amplifier with gain of 3 is used since the offset requirement from it is 15mV. Hence, Stage 2 of the proposed ADC doesn't require the output offset compensation. The total capacitance from the second ADC is 11C.

Preamp


Asim Khan
email: asimkhan@kaist.ac.kr

Muhammad Umar
email: umar@kaist.ac.kr

Karim Khan

Muhammad Bilal
email: bilalm@kaist.ac.kr

Chong-Min Kyung
email: kyung@kaist.ac.kr

A Hardware Accelerator for Real Time Sliding Window Based Pedestrian Detection on High Resolution Images

Keywords: FPGA, Low Power, Object Detection, Real-Time

Pedestrian detection has lately attracted considerable interest from researchers due to many practical applications. However, the low accuracy and high complexity of pedestrian detection has still not enabled its use in successful commercial applications. In this chapter, we present insights into the complexity-accuracy relationship of pedestrian detection. We consider the Histogram of Oriented Gradients (HOG) scheme with linear Support Vector Machine (LinSVM) as a benchmark. We describe parallel implementations of various blocks of the pedestrian detection system which are designed for full-HD (1920x1080) resolution. Features are improved by optimal selection of cell size and histogram bins which have been shown to significantly affect the accuracy and complexity of pedestrian detection. It is seen that with a careful choice of these parameters a frame rate of 39.2 fps is achieved with a negligible loss in accuracy which is 16.3x and 3.8x higher than state of the art GPU and FPGA implementations respectively. Moreover 97.14% and 10.2% reduction in energy consumption is observed to process one frame. Finally, features are further enhanced by removing petty gradients in histograms which result in loss of accuracy. This increases the frame rate to 42.7 fps (18x and 4.1x higher) and lowers the energy consumption by 97.34% and 16.4% while improving the accuracy by 2% as compared to state of the art GPU and FPGA implementations respectively.

Introduction

Researchers in industry and academia have been striving for accurate and real-time pedestrian detection (PD) for more than a decade owing to many commercial and military applications. Industries such as surveillance, robotics, and entertainment will be greatly influenced by appropriate application of PD. Advanced driver assistance systems (ADAS) and unmanned ground vehicles (UGV) are merely a distant dream without automated pedestrian detection. The fact that more than 15% of traffic accidents include pedestrians [START_REF] Shankar | Pedestrian roadway fatalities[END_REF] shows the importance of real-time pedestrian detection for the modern society [START_REF] Geronimo | Survey detection for advanced driver assistance systems[END_REF]. Amid numerous applications, the search for an accurate yet fast PD algorithm is ongoing. Researchers have shown great interest over the past few years in extracting diverse features from an image and finding an appropriate classification method to perform robust PD [START_REF] Khan | Hardware architecture and optimization of sliding window based pedestrian detection on FPGA for high resolution images by varying local features[END_REF][START_REF] Papageorgiou | A trainable system for object detection[END_REF][START_REF] Oren | Pedestrian detection using wavelet templates[END_REF][START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF][START_REF] Cheng | Pedestrian detection using sparse Gabor filter and support vector machine[END_REF]. However, the histogram of oriented gradients (HOG) approach has proven to be a groundbreaking effort, and has shown good accuracy in various illumination conditions and multiple textured objects. Inspired from SIFT [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF], the authors in their seminal paper [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF] present a set of features over a dense grid in a search window. For training and classification, they used the linear support vector machine (linSVM). Their work inspired many other researchers and is still used as a benchmark PD scheme.

Although HOG was presented many years back, it is surprising to see that very few efforts have been made for an optimal hardware implementation of HOG. In fact, most of the research has been targeting pedestrian detection on a high end CPU or GPU or combination of both [24][START_REF] Sudowe | Efficient use of geometric constraints for sliding-window object detection in video[END_REF][START_REF] Machida | GPU & CPU cooperative accelerated pedestrian and vehicle detection[END_REF][START_REF] Yan-Ping | Fast HOG feature computation based on CUDA[END_REF][START_REF] Bilgic | Fast human detection with cascaded ensembles on the GPU[END_REF][START_REF] Prisacariu | fastHOG -a real-time GPU implementation of HOG[END_REF]. Field Programmable Gate Arrays (FPGA) and Application Specific Integrated Circuits (ASIC) often provide better execution speed and energy efficiency as compared to GPUs due to deep pipelined architectures. Furthermore, in many embedded applications, such as surveillance, there are numerous constraints on hardware cost, speed, and power consumption. For such applications, it is more suitable to use task-specific (FPGA, ASIC) rather than general-purpose platforms. Moreover, to meet such constraints, certain parameters of the algorithm need to be tuned and an insight is required into how the change of parameters of PD affects not only the accuracy but also the hardware complexity.

Efforts have been made in the research community to either improve the accuracy of PD or reduce the hardware complexity of HOG. In [START_REF] Mizuno | Architectural study of HOG feature extraction processor for real-time object detection[END_REF] and [START_REF] Takagi | A sub-100-milliwatt dual-core HOG accelerator VLSI for real-time multiple object detection[END_REF], the computational complexity of HOG is reduced with cell-based scanning and simultaneous SVM calculation using FPGA and ASIC implementations for full HD resolution; however, the implementations use the parameters as suggested in [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF]. Various hardware optimizations are presented in [START_REF] Chen | An Efficient Hardware Implementation of HOG Feature Extraction for Human Detection[END_REF][START_REF] Lee | Accelerating histograms of oriented gradients descriptor extraction for pedestrian recognition[END_REF][START_REF] Pang | Efficient HOG human detection[END_REF][START_REF] Hiromoto | Hardware architecture for high-accuracy real-time pedestrian detection with CoHOG features[END_REF][START_REF] Bauer | FPGA-GPU architecture for kernel SVM pedestrian detection[END_REF][START_REF] Negi | Deep pipelined one-chip FPGA implementation of a real-time image-based human detection algorithm[END_REF][START_REF] Hahnle | FPGA based real-time pedestrian detection on high-resolution images[END_REF][START_REF] Blair | Characterizing a heterogeneous system for person detection in video using histograms of oriented gradients: Power versus speed versus accuracy[END_REF] for an efficient pedestrian detection system. However, for real-time PD with power and area constraints, it is imminent to find the set of parameters of HOG that provide the best compromise in terms of computational complexity and accuracy. Recently, a hardware architecture for fixed point HOG implementation has been presented [START_REF] Ma | Evaluation and Acceleration of High-Throughput Fixed-Point Object Detection on FPGAs[END_REF] where the bit-width has been optimized to achieve significant improvement in power and throughput. We believe that in addition to bit-width there are other parameters which need to be optimized to provide a holistic understanding of the relationship between accuracy, speed, power, and complexity. Moreover, sliding window based pedestrian detection requires detection to be performed at multiple scales of image. It has been shown that the best detection performance can be achieved with scale factor (the ratio to scale the image after each detection) of at-least 1.09. This results in processing around 45 scales for full-HD resolution. As shown in Fig. 1, a combination of the number of scales (=45) required for maximum accuracy [START_REF] Ma | Evaluation and Acceleration of High-Throughput Fixed-Point Object Detection on FPGAs[END_REF] - [START_REF] Dollar | Pedestrian detection: An evaluation of the state of the art[END_REF] and throughput for real-time pedestrian detection at full-HD resolution has not been achieved before.

The key contributions of our work can be summarized as follows.

• We present parallel implementation of various blocks of HOG-based PD on an FPGA. Parallel implementation has been used to improve the speed of PD. • We derive the accuracy, speed, power, and hardware complexity results of HOGbased PD with different choices of cell sizes and number of histogram bins. • We show that by using the right choice of cell size and number of histogram bins, a significant reduction in power consumption and increase in throughput can be achieved with reasonable accuracy. • Finally features are refined by removing insignificant gradients which results in not only improvement of throughput and power consumption but also accuracy.

This chapter is an extension of our original paper [START_REF] Khan | Hardware architecture and optimization of sliding window based pedestrian detection on FPGA for high resolution images by varying local features[END_REF] including more detailed literature survey and hardware implementation details. The rest of the chapter is organized as follows. Section 2 summarizes the state of the art in PD. In Section 3, a brief overview of HOG is presented. The proposed hardware implementation is discussed in Section 4. In Section 5, the accuracy, speed, power, and hardware complexity results are shown for different choices of parameters and the optimal choice of parameters under given constraints is described. Section 6 concludes the work.

Literature Survey

Numerous efforts have been made in the past to perform PD efficiently. An extensive survey of PD schemes is given in [START_REF] Dollar | Pedestrian detection: An evaluation of the state of the art[END_REF]. Generally, these approaches can be classified into two categories: segmentation-based approaches [START_REF] Gu | Recog. using regions[END_REF] and sliding window-based approaches [START_REF] Papageorgiou | A trainable system for object detection[END_REF]. A segmentation-based approach processes the whole frame at once and extracts segments of the frame which include pedestrians. On the other hand, sliding window-based approaches divide a frame into multiple, overlapping windows and search pedestrians in each of these windows.

2.1

Sliding Window Based Pedestrian Detection

Recently, researchers have put more effort into sliding window approach as this approach simplifies the problem of PD to binary classification in a given window. Sliding window-based approaches can be further subdivided into rigid and part-based methods. The rigid schemes consider the window holistically to identify a pedestrian. Part-based schemes, such as [START_REF] Felzenszwalb | A discriminatively trained, multiscale, deformable part model[END_REF][START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF] identify different parts of a pedestrian in a window, and decide the presence of a pedestrian based on the location and confidence (accuracy) of detected parts. Part-based schemes have been shown to perform better compared to rigid schemes as the decision in these methods is based on the aggregate of decisions for different parts and these schemes can handle occlusion better compared to rigid schemes. However, the higher computational complexity of partbased methods makes them infeasible for real-time applications. Rigid schemes utilize a single feature or multiple features to detect an object. We have categorized the schemes depending on the feature and implementation platform.

Single Feature Pedestrian Detection. In [START_REF] Papageorgiou | A trainable system for object detection[END_REF], the authors use Haar-like features with Support Vector Machines (SVM) to identify objects in a scene. Their method was advanced in [START_REF] Porikli | Integral histogram: A fast way to extract histograms in cartesian spaces[END_REF] for face detection, where the authors obtained an astounding increase in speed by using integral images to compute Haar-like features. Furthermore, cascaded boosted trees were used for classification. The method of [START_REF] Porikli | Integral histogram: A fast way to extract histograms in cartesian spaces[END_REF] was used for PD in [START_REF] Viola | Detecting pedestrians using patterns of motion and appearance[END_REF]. However, using Haar-like features for PD detection did not show much promise until recently [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF] due to their low accuracy. A set of rich and compact features was required to improve PD. Rich features were needed to extract maximum information from a window and compactness was needed to better generalize from training to testing. HOG [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF] performed both these tasks by including the complete (or rich) gradient information of a window into compact histograms. They trained Linear Support Vector Machine (LinSVM) framework for classification. Furthermore, they developed and used the INRIA pedestrian dataset, which was the most extensive dataset for PD at that time. Resultantly, their method achieved significant improvement in accuracy of PD compared to the previous schemes.

Since its inception, HOG has influenced most of the modern PD methods. In [START_REF] Sabzmeydani | Detecting pedestrians by learning shapelet features[END_REF], gradients in local patches, similar to HOG, are used to represent shape descriptors. These shape descriptors are combined to create a single feature which is classified using boosted trees. The method is used for PD as well as detection of other objects. Edgelets, used in [START_REF] Wu | Detection of multiple, partially occluded humans in a single image by bayesian combination of edgelet part det[END_REF] and [START_REF] Wu | Cluster boosted tree classifier for multi-view, multi-pose object detection[END_REF], have been used to learn and classify body parts with boosted trees. Other variations include distance transform and template hierarchy [START_REF] Gavrila | A bayesian, exemplar-based approach to hierarchical shape matching[END_REF] to match images with templates, granularity-tunable gradients partition to define spatial and angular uncertainty of line segments [START_REF] Liu | Granularitytunable gradients partition descriptors for human det[END_REF] and its extension to spatiotemporal domain [START_REF] Liu | Spatial-temporal granularity-tunable gradients partition descriptors for human det[END_REF], shape features [START_REF] Gavrila | Real-time object det. for smart vehicles[END_REF] and finally motion based features [START_REF] Dalal | Human detection using oriented histograms of flow and appearance[END_REF]- [START_REF] Wojek | Multi-cue onboard pedestrian detection[END_REF].

Multiple Feature Pedestrian Detection. To further enhance the PD accuracy of HOG, researchers have complimented HOG with other features. Local Binary Pattern (LBP) is a very simple feature based on magnitude comparison of surrounding pixels, and has typically been used for texture classification [START_REF] Ojala | Multiresolution grayscale and rotation invariant texture classification with local binary patterns[END_REF] and face detection [50]. It has also been used in PD [START_REF] Zheng | Effective pedestrian detection using center-symmetric Local Binary/Trinary Patterns[END_REF]. In [START_REF] Wang | An hog-lbp human detector with partial occlusion handling[END_REF], the authors present a feature combining both HOG and LBP and use linSVM for classification. They show that this combination improves the PD performance under partial occlusion. In [START_REF] Ott | Implicit color segmentation features for pedestrian and object detection[END_REF], the authors use implicit segmentation and divide the image into separate foreground and background, followed by HOG. HOG, LBP and local ternary patterns were combined in [START_REF] Hussain | Feature sets and dimensionality reduction for visual object det[END_REF] for pedestrian and object detection. Gradients information and HOG, textures (cooccurrence matrices), and color frequency are combined in [START_REF] Schwartz | Human detection using partial least squares analysis[END_REF]. Partial least squares are used to reduce the dimensions of the feature and SVM is used for classification. HOG has been combined with Haar-like [START_REF] Wojek | A performance evaluation of single and multi-feature people detection[END_REF], shapelets [START_REF] Sabzmeydani | Detecting pedestrians by learning shapelet features[END_REF], color self-similarity and motion [START_REF] Walk | New features and insights for pedestrian detection[END_REF] features as well. Note that none of these features when used independently from HOG has been able to outperform HOG.

Real Time Pedestrian Detection

Numerous applications require PD at fast rates. For such applications, it is more suitable to use task-specific (GPU, FPGA, ASIC) rather than general-purpose platforms. A fine grain parallel ASIC implementation of HOG-based PD is presented in [START_REF] Takagi | A sub-100-milliwatt dual-core HOG accelerator VLSI for real-time multiple object detection[END_REF]. In [START_REF] Chen | An Efficient Hardware Implementation of HOG Feature Extraction for Human Detection[END_REF], simplified methods are presented for division and square root operations for use in HOG. However, by employing their methods, the accuracy of PD is severely degraded. A multiprocessor system on chip (SoC) based hardware accelerator for HOG feature extraction is described in [START_REF] Lee | Accelerating histograms of oriented gradients descriptor extraction for pedestrian recognition[END_REF]. In [START_REF] Pang | Efficient HOG human detection[END_REF], the authors reuse the features in blocks to construct the HOG features of overlapping regions in detection windows and then use interpolation to efficiently compute the HOG features for each window.

In [START_REF] Hiromoto | Hardware architecture for high-accuracy real-time pedestrian detection with CoHOG features[END_REF], the authors developed an efficient FPGA implementation of HOG to detect traffic signs. In [START_REF] Bauer | FPGA-GPU architecture for kernel SVM pedestrian detection[END_REF], a real-time PD framework is presented which utilizes an FPGA for feature extraction and a GPU for classification. A deep-pipelined single chip FPGA implementation of PD using binary HOG with decision tree classifiers is discussed in [START_REF] Negi | Deep pipelined one-chip FPGA implementation of a real-time image-based human detection algorithm[END_REF]. A heterogeneous system is presented in [START_REF] Blair | Characterizing a heterogeneous system for person detection in video using histograms of oriented gradients: Power versus speed versus accuracy[END_REF] to optimize the power, speed and accuracy.

From the discussion above, we notice that HOG is integral to most PD algorithms. Efforts have been made in the research community to either improve the accuracy of PD or reduce the hardware complexity of HOG. In our study, we are yet to find an effort which analyzes the effects of reducing hardware costs on accuracy of HOG. For real-time PD with power and area constraints, it is imminent to find the set of parameters of HOG that provide the best compromise in terms of computational complexity and accuracy.

Overview of HOG

In this section, we present a brief overview of the HOG algorithm for PD. Although HOG can be used in a part-based PD scheme, we limit our discussion to the rigid HOG as described in the original paper [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF]. A block diagram showing functional blocks of the algorithm is shown in Fig. 2.

In HOG, a search window is divided into multiple overlapping blocks which are further divided into cells as shown in Fig. 3.,where 𝑤 ! , ℎ ! , 𝑤 ! , ℎ ! , 𝑤 ! , ℎ ! , 𝑤 ! , ℎ ! , are the frame, window, block and cell (width, height) respectively. 𝑁 !"# is the number of histogram bins. The blocks have an overlap of 50%, creating a dense grid over the search window. So a single 𝑤 ! ×ℎ ! window has

𝑛 ! = 𝑤 ! /𝑤 ! ×ℎ ! / ℎ ! cells and 𝑛 ! = ! ! !! ! ! ! × ! ! !! ! ! !
blocks. Gradient features are extracted from these blocks and cells, and are concatenated to create a single feature vector for the whole window.

A filter with coefficients [-1, 0, 1] is applied to the window in horizontal and vertical directions, creating the images 𝐺 ! and 𝐺 ! , respectively. These images are used to generate the gradient magnitude image, 𝐺 ! , and the gradient orientation image, 𝐺 ! , for each pixel 𝑥, 𝑦 as follows. The histogram used in the feature accumulates the orientation information of an image. Each histogram has multiple bins, where each bin represents a specific orientation in the interval [0, π). The value 𝐺 ! (𝑥, 𝑦) is added to the bin of the histogram which corresponds to 𝐺 ! (𝑥, 𝑦). Such histograms are developed for every cell of the window, as shown in Fig. 3.

𝐺 ! 𝑥, 𝑦 = 𝐺 𝑥, 𝑦 = 𝐺 ! 𝑥, 𝑦 ! + 𝐺 ! 𝑥, 𝑦 ! (1)
𝐺 ! 𝑥, 𝑦 = tan !! ! ! !,! ! ! !,! (2)
The cell histograms belonging to a single block are concatenated to form block histogram of length 𝑀 = 4 ×𝑁 !"# , where, 𝑁 !"# is the number of bins in each cell histogram. Block histograms are further L2-normalized using (3), and then added to the feature vector. L2-norm for an un-normalized feature vector v, is given by,

𝑥 ! ! = ! ! ! ! ! ! ! ! ! . ( 3
)
where

𝑖 = 1, … , 𝑀 , 𝑏 = 1, … , 𝑛 ! , 𝑣 ! ! = 𝑣 ! ! + 𝑣 ! ! + ⋯ + 𝑣 ! !
and 𝜀 is a small constant to avoid division by zero. L2-normalization is performed to improve robustness against illumination changes.

For classification, LinSVM is used. From an implementation perspective, a weight vector is obtained after the training stage. During classification, a dot product of the feature extracted from the window and the weight vector is compared against a threshold. If the dot product is greater than the threshold, then a pedestrian is identified.

4

Hardware Architecture

The hardware implementation of HOG presents a unique challenge, which is quite distinct from the software implementation. First, we cannot store and access a complete frame, and read and write from multiple addresses at once as this will require unrealistically large hardware resources. Second, floating point operations are quite costly in hardware, as they use more FPGA area and runs at a lower frequency; therefore, we avoid them in hardware implementation. Finally, the choice of parameters affects hardware complexity significantly compared to software implementation. Our key objectives in this implementation are to maintain the maximum accuracy and minimum power consumption while performing real time PD by controlling local features. Hardware/memory optimization is done using optimal values of these features. The optimized architecture thus obtained results in a reduced workload and low bandwidth.

The conceptual block diagram of the proposed HOG Accelerator (HOG-Acc) is shown in Fig. 4. In the following we present a description of the major functional blocks shown in Fig. 4.

Gradient Computation

To compute the gradient magnitude and orientation, the horizontal and vertical gradient images, i.e., 𝐺 ! and 𝐺 ! , need to be generated. Gradient is computed over the 3x3 neighborhood of each pixel; therefore, two line buffers are required to store two consecutive scan lines of the image to maintain a 3x3 neighborhood of every pixel.

A straight forward computation of the gradient magnitude, as given in (1), will require the implementation of the square root operation, which will consume significant hardware resources; thereby, delay and power consumption will increase. In order to reduce the computational complexity, the following approximations from [START_REF] Chen | An Efficient Hardware Implementation of HOG Feature Extraction for Human Detection[END_REF] have been used to compute the gradient magnitude and orientation.

𝐺 ! 𝑥, 𝑦 ≈ max 0.875𝑎 + 0.5𝑏 , 𝑎 , (4)
where,

𝑎 = max 𝐺 ! 𝑥, 𝑦 , 𝐺 ! 𝑥, 𝑦 , (5)
and The circuitry for gradient magnitude computation is shown in Fig. 5. Equation ( 5) and ( 6) are implemented using a single compare operation, while (4) requires four shift operations yielding 0.875a and 0.5b, then an adder and one more comparator is used to give the final gradient magnitude. Similarly, a direct implementation of (2) for computing the gradient orientation will require two costly hardware operations: the inverse tangent and division. To reduce the complexity, (2) can be rewritten as

𝑏 = min 𝐺 ! 𝑥, 𝑦 , 𝐺 ! 𝑥, 𝑦 . (6)
𝐺 ! 𝑥, 𝑦 tan 𝐺 ! 𝑥, 𝑦 = 𝐺 ! 𝑥, 𝑦 . ( 7
)
The problem of identifying the gradient orientation can be solved using [START_REF] Takagi | A sub-100-milliwatt dual-core HOG accelerator VLSI for real-time multiple object detection[END_REF] as: multiplying the horizontal gradient value with the values of the right column of table I; the product which best matches against the vertical gradient indicates the gradient of the pixel. Note that even the multiplication operation is not required, as the product with the values in the right column of Table I can be performed by simple arithmetic shifting.

The circuit to compute the histogram bin is shown in Fig. 6. It consists of two parts, one deals with the quadrant decision and other decides the bin. Comparing horizontal and vertical neighboring pixels sets the Q-flag value which indicates whether the bin lies in first or second quadrant. Once we know the quadrant, we have to decide which histogram bin the orientation value lies in. By using Table I to approximate the value of tangent function at different orientations, complex Fig. 6. Bin Computation Module: Bin quadrant is decided using a Q-flag, which is computed by comparing horizontal and vertical pixels, histogram bin is then decided implementing (7) using comparators and AND gate.

𝑡𝑎𝑛0 ° 0 𝑡𝑎𝑛10 ° 2 !! + 2 !! 𝑡𝑎𝑛20 ° 2 !! + 2 !! 𝑡𝑎𝑛30 ° 2 !! + 2 !! + 2 !! 𝑡𝑎𝑛40 ° 2 !! + 2 !! + 2 !!
operations such as inverse tangent and division can be avoided. The hardware utilizes only comparators, shifters and adders, hence reducing the complexity significantly. It has been shown in [START_REF] Ma | Evaluation and Acceleration of High-Throughput Fixed-Point Object Detection on FPGAs[END_REF] that bit-width assigned to magnitude has a significant impact on accuracy, throughput and power consumption as it affects the data sizes at all the next stages. In [START_REF] Ma | Evaluation and Acceleration of High-Throughput Fixed-Point Object Detection on FPGAs[END_REF] fixed-point implementation is considered and bit width of gradient magnitude is optimized as 13 bits (9:4 (integer: fractional)). We argue that using only integer values of gradient magnitude can further improve the accuracy, throughput and power consumption. The details are given in Section IV. The key insight is that by using integer values for gradient magnitudes, we can remove the histogram values which are less significant. The advantages are twofold. 1) It reduces the hardware complexity due to reduced bit width and integer operations. 2) It improves the accuracy because removing these petty gradient magnitudes enhances the feature vector for training and classification.

Cell Histogram Generation

We propose a parallel Cell Histogram Generation (CHG) module as shown in Fig. 7. Gradient magnitudes and orientation bins for every 𝑤 ! ×ℎ ! pixels are given as input to CHG. Decoders and adders are used to build the histogram. Each bin value is given as input to the decoder. Only one output is set to '1' corresponding to the specific bin; gradient magnitude for that bin hence propagates to the input of adder, where all the magnitudes of the same bin are added.

The decoder size is dependent on the number of bits required to represent single bin, i.e. if number of histogram bins increase the size of decoder increases. On the other hand, the cell size (𝐶 !"#$ = 𝑤 ! × ℎ ! ) affects the number of decoders as the total number of decoders required equals 𝐶 !"#$ . Multipliers required for CHG are dependent on both 𝑁 !"# and 𝐶 !"#$ . Multipliers in each stage depend on 𝑁 !"# while number of stages depends on 𝐶 !"#$ . Finally, the number of adders is equivalent to the 𝑁 !"# chosen. Adder size, however, varies according to 𝐶 !"#$ . We can clearly see that the complexity of CHG is strongly dependent on 𝑁 !"# and 𝐶 !"#$ .

Since pixels are coming row by row, we have to maintain cell histograms for multiple blocks and windows as each row has multiple windows. Therefore, the gradient magnitudes and orientations computed for every 𝑤 ! pixels (one cell) are concatenated and stored in memory. Pixels of row index which is a multiple of ℎ ! indicate the completeness of cell. This row is directly stored into registers. At the start of every such row, respective values of previous rows for the particular cell are read into registers from block RAM every clock cycle. As we have considered 𝑤 ! = ℎ ! the cell completes in horizontal and vertical directions simultaneously. Hence, the number of shift registers required is equivalent to ℎ ! . Each shift register stores magnitudes and bins for 𝑤 ! pixels. After 𝑤 ! cycles the data of one cell is completed so it is shifted to the memory, which in turn writes the data for the previous row in the next register. The resultant cell histogram is given to the next stage for processing. This is done every time the new cell is completed. i.e; when the row index is a multiple of ℎ ! and column index is a multiple of 𝑤 ! . The cell histograms for multiple windows in a frame are stored in memory while they are shifted to registers for each active window (the window whose cells histograms are completed).

Block Histogram Normalization

Cell histograms are maintained in the memory till four neighboring cells are completed and a block is obtained. Note that the memory required to store the cell histograms increases with smaller cells (more cells per row and column) and larger number of histogram bins for every cell (more data per cell). In other words, 𝐶 !"#$ affects the memory locations required while 𝑁 !"# influences the width of each location. The histogram is normalized using the Block Histogram Normalization Engine (BHN) shown in Fig. 8. Normalization is performed every time a new block is completed. Each histogram value in a block is squared and added. The sum is given as input to inverse square root module which is approximated using "fast inverse square root" algorithm [30]. In summary, logical shifting, subtraction and finally one iteration of Newton's method approximates the inverse square root. Finally, the result of inverse It is seen that the number of multipliers in BHN depends on the size of the block histogram, which is related to number of bins assigned to each cell histogram. Adding a single bin to cell histogram adds eight multipliers to the hardware. The adder size also increases proportionately.

SVM Classification

The normalized histograms obtained from the BHN block are again stored in the memory. Once normalized histograms for the whole window are available classification can be performed which can consume a amount of memory.

Performing classification for the whole window at once also requires a large number of multipliers and adders. The situation gets worse as the feature vector size increases with smaller cell sizes or large number of bins. Therefore, we have opted for partial classification by dividing the classification for the whole window into multiple stages. The hardware shown in Fig. 9. is reused at every stage. The strategy behind reusing the hardware is very straightforward. Since it takes 𝑤 ! cycles to completely process a cell, we have reused the same hardware over these 𝑤 ! cycles doing partial classification every 𝑁 ! 𝑤 ! blocks. So the number of partial classification stages is equal to 𝐶 ! . The results of each stage are accumulated to get the final classification result.

The key observation is that the cell size effects the hardware complexity in two ways. First, it has a direct impact on feature vector size. Second, larger the cell size, more cycles will be available to perform classification, thereby, smaller hardware is required for partial classification.

Results and Discussion

In this section, we evaluate our hardware implementation for multiple cell sizes and histogram bins to obtain optimal set of these parameters. Results are presented for full-HD (1920x1080) resolution videos. Window size is considered to be 64x128. Block size is 2x2 cells, while block and window step size is one cell for both horizontal and vertical directions. Scale factor to rescale images is set to 1.05. This results in 45 scales to be processed per frame. Other parameters depend on the choice of cell size and histogram bins.

Here, we first present our experimental setup then we analyze the effect of different cell sizes and histogram bins on accuracy, throughput and power. Using these results, parameters yielding least power and maximum throughput with negligible loss in accuracy are selected. Finally, using these parameters comparison with the state of the art object detection implementations is presented.

Experimental Setup

We have implemented our system on Xilinx Virtex 7 (XC7VX485T) FPGA. There are 75,900 slices, 607,200 Configurable Logic Blocks (CLBs) and 485,760 logic cells in this FPGA. Moreover, 37,080 Kb block RAM and 2,800 DSP slices are present. Image rescaling and window sampling is done for positive and negative images and then sent to HOG-Acc for processing which returns the detection result. Processing 45 scales requires a large amount of memory and pipelined stages so we have utilized the time multiplexing approach of [START_REF] Hahnle | FPGA based real-time pedestrian detection on high-resolution images[END_REF]. The host software is written using Visual Studio 2012 and Verilog is used for HOG-Acc design. Design is synthesized using Xilinx ISE 14.7 and along with Modelsim 10.2, a hardware/software co-simulation is performed to verify the implementation functionality.

Accuracy Analysis

We have used INRIA dataset [START_REF]INRIA Person Dataset[END_REF], to evaluate our HOG implementation. There are several other datasets available for pedestrian detection evaluation like Caltech [START_REF] Dollar | Pedestrian detection: A benchmark[END_REF], ETH [START_REF] Enzweiler | Monocular pedestrian detection: Survey and experiments[END_REF], and Daimler [START_REF] Ess | A mobile vision system for robust multi-person tracking[END_REF]. We have, however, restricted our results to INRIA because it provides us with a reasonable variety of images with different poses and backgrounds so these results can be generalized to other datasets and real life scenarios.

All detection results are collected, and afterwards recall is calculated from number of true positives (TP) and false negatives (FN) as shown in [START_REF] Ma | Evaluation and Acceleration of High-Throughput Fixed-Point Object Detection on FPGAs[END_REF].

𝑅𝑒𝑐𝑎𝑙𝑙 = !" !"!!" (8)
A false positive per window (FPPW) of 10 -4 is mostly considered in literature for pedestrian detection results. We also present the Miss Rate (1-Recall) results for FPPW = 10 -4 for multiple cell sizes and number of bins. The results are shown in Fig. 10. It is seen that generally larger histogram bins gives better detection rates. This is obvious, as more histogram bins allow fine division gradient orientations, hence better feature vector for training and classification. On the other hand, improvement is seen in detection rates by increasing cell size up to a certain value and it drops increasing cell sizes too much. Smaller cell sizes provide a dense grid of blocks and windows in a frame, therefore, using smaller cells would improve accuracy. However, using too small cell sizes results in degraded performance because there are not enough distinguishing features within the cells. Minimum miss rate of 12% is achieved at (𝐶 !"#$ , 𝑁 !"# ) = (7x7, 11).

Throughput and Power Consumption Analysis

Power consumption and throughput are directly related to the hardware resources used.

In the previous section it is seen that the cell size and histogram bins has significant impact on hardware complexity. The effect on different hardware components for different cell sizes and number of bins for a single core is shown in Fig. 11. We see a significant reduction in hardware resources by increasing cell size or reducing number of bins. The reasons being discussed in previous section for independent blocks. Number of frames processed per second (fps) is dependent on the maximum frequency at which the hardware can operate. In our hardware architecture it is mainly dependent on the size of partial classification engine and the block normalization engine. As discussed in previous section, the complexity of PCE is heavily dependent on 𝐶 !"#$ while that of BHN depends on both 𝐶 !"#$ and 𝑁 !"# . Fig. 12 shows the results. We get the maximum frequency at the point where both PCE and BHN have overall minimal hardware complexity. Specifically, the (𝐶 !"#$ , 𝑁 !"# ) = (11x11, 6).

We have used Xilinx Xpower analyzer (XPA) 14.7 to estimate the deviations in power consumption by varying the parameters. We have simulated the hardware and created 'Value Change Dump' (vcd) files are used to set the toggle rates of all signals.

Post place and route results are obtained and are shown in Fig. 13. Power consumption increases by reducing the cell size or increasing the histogram bins. This is fairly understandable due to the fact that both these parameters increase the hardware complexity due to increase in the feature vector size. Minimum power consumption is 9.98 W with (𝐶 !"#$ , 𝑁 !"# ) = (12x12, 6), the maximum cell size and minimum histogram bins as expected.

Choice of Parameters

We have seen from the previous analysis that there does not exist a set of parameters which give us best accuracy, power and throughput. Improving the accuracy worsens the power and throughput while maintaining minimum power and maximum throughput severely degrades the accuracy. Similarly, trying to improve throughput may degrade power consumption significantly and vice versa. However, accuracy is changing very slightly at certain regions in Fig. 9. Similarly, there are more than one sets of parameters which give almost the same power consumption. This allows us to select the best of one of these metrics while slightly compromising on another metric. We can achieve best results by selecting (𝐶 !"#$ , 𝑁 !"# ) = (9x9, 10). Further we obtained results for miss rate by changing bit-width for this optimal parameter set. The results are shown in Fig. 14. Bit-width is hence set to eight bits as it gives maximum accuracy and minimum hardware complexity. Note that this further results in reduced bit-width in all the next blocks. Parameters optimized for low power and high speed are shown in Table II & III comparing the throughput and energy consumption results with the other state of the art FPGA and GPU implementations. We have presented three results. 1) HOG CONV , which shows the results for conventionally used parameters. We can achieve 32 fps for full-HD while dissipating 0.656 J/frame and 15% miss rate. 2) HOG OCB , presents results for optimized cell size and histogram bins. Frame rate achieved by optimizing cell size and histogram bins is 39.2 fps with energy consumption of 0.484 J/frame while maintaining a miss rate at 15%. Gradient magnitude bit-width is considered to be 13 bits. 3) Finally, HOG OCB-RF , in which features are further refined by removing insignificant gradients, is presented. This results in a frame rate of 42.7 fps while energy consumption is 0.45 J/frame at 13% miss rate.

Conclusion

We have presented fully parallel architectures for various modules of pedestrian detection system utilizing Histogram of oriented gradients (HOG). HOG has shown high detection accuracy but the detection speed and power consumption are major bottlenecks for real time embedded applications. We have optimized parameters, cell size and histogram bins, to achieve low power and high throughput while maintaining the detection accuracy. Feature refinement is done to further improve the results. Combination of optimal parameters and our hardware accelerator results in a frame rate of 42.7 fps for full-HD resolution and lowers the energy consumption by 97.34% and 16.4% while improving the accuracy by 2% as compared to state of the art GPU and FPGA implementations respectively. This work can be extended to use multiple cores on a single FPGA or using multiple FPGAs to further increase throughput while an ASIC implementation would greatly reduce the power consumption. It can also be extended to include other features and classifiers or combinations of those to optimize for objects other than pedestrians.

Fig. 1 .

 1 Fig. 1. Comparison of the state of the art in terms of frames per second and number of scales.

Fig. 2 .

 2 Fig. 2. Block Diagram of HOG based Pedestrian Detection

Fig. 3 .

 3 Fig. 3. A depiction of image division for sliding window based object detection. An input image (w F × h F ) is divided into overlapping windows. The window is divided into overlapping blocks which are further divided into cells. A histogram is generated for every cell.

Fig. 4 .

 4 Fig. 4. Block Diagram of Hardware Architecture. Gradient is computed over input pixels stored in Pixel Line buffer, cell histograms are then built using gradients, SRAM is used to store intermediate cell histograms. Next steps are normalization of histograms generated and finally classification.

Fig. 5 .

 5 Fig. 5. Gradient Magnitude Computation Module. (a) Simply subtract the horizontal and vertical neighboring pixels to compute the horizontal and vertical gradients. (b) Gradient magnitude is computed by shift and compare operations to implement (4) -[START_REF] Mizuno | Architectural study of HOG feature extraction processor for real-time object detection[END_REF]

Fig. 7 .

 7 Fig. 7. Cell Histogram Generation (CHG) Engine: Histogram bins and gradient magnitudes are given as input and cell histograms are generated.

Fig. 8 .

 8 Fig. 8. Block Histogram Normalization (BHN) Engine: Un-normalized Block histograms (concatenated cell histograms) are used as inputs to generate normalized block histograms.

Fig. 9 .

 9 Fig. 9. Partial Classification Engine (PCE), single stage of LinSVM classification to be performed for whole window. Inputs are normalized histograms while output is the partial classification result.

Fig. 10 .

 10 Fig. 10. Accuracy Analysis, miss rate generally reduces with increasing cell sizes and decreasing number of bins

Fig. 11 .

 11 Fig. 11. Hardware Utilization Comparison. Breakdown of usage of multiple slices of Xilinx FPGA with varying cell size and histogram bins. Increasing any one of them results in increased hardware complexity.

Fig. 12 .

 12 Fig. 12. Throughput Analysis, an increase in throughput is seen for bigger cell sizes and histogram bins.

Fig. 13 .

 13 Fig. 13. Power Consumption Analysis, Large cell size and smaller number of histogram bins results in low power consumption.

Fig. 14 .

 14 Fig. 14. Variation in miss rate for (𝐶 !"#$ , 𝑁 !"# ) = (9x9, 10).

TABLE I APPROXIMATED

 I VALUES OF TANΘ

	Tangent	Approximated Value

TABLE II COMPARISON

 II OF PARAMETERS AND THROUGHPUT FOR VARIOUS GPU AND FPGA

				IMPLEMENTATIONS
		Cell Size	Histogram Bins	Win. Stride	# scales	Resolution Windows/frame FPS
				GPU Implementation
	[22], [24] 8x8	9	8	37 1024x768	-	17
	[25]	8x8	-	-	>1 640x480	4,096	57
	[26]	8x8	8	2	>1 640x480	50,000	23.8
	[27]	8x8	9	8	1	640x480	-	32
	[28]	8x8	9	4	>1 1280x960	150,000	2.4
	[29]	8x8	9	-	>1 640x480	-	5.6
				FPGA Implementation
	[18]	8x8	8	4	>1 320x240	3,615	38
	[19]	8x8	9	-	1	800x600	1000	>10
	[20]	8x8	8	9	1	640x480	1,540	62.5
	[21]	8x8	9	8	18 1920x1080	27,960	64 (esti-mated)
	[22]	8x8	9	8	13 1024x768	20,868	13
	[23]	8x8	8	4	>1 640x480	56,466	30 (esti-mated)
	[6]	8x8	9	8	1	800x600	5,580	72
	[8]	8x8	9	4	34 640x480	121,210	68.18
	[8]	8x8	9	4	34 1600x1200 1,049,886	10.41 (estimated)
	HOGCONV 8x8	9	8	45 1920x1080	264,062	32
	HOGOCB 9x9	10	8	45 1920x1080	264,062	39.2
	HOGOCB-RF 9x9	10	8	45 1920x1080	264,062	42.7

TABLE III COMPARISON

 III OF PARAMETERS AND ENERGY CONSUMPTION FOR VARIOUS GPU AND FPGA IMPLEMENTATIONS

	Cell Size	Histogram Bins	Win. Stride	# scales	Resolution Windows/frame	Power (W)	Energy (J/Frame)
	[8] (GPU) 8x8	9	4	34 640x480	121,210	225	17
	[8](FPGA) 8x8	9	4	34 640x480	121,210	37	0.54
	HOGCONV 8x8	9	8	45 1920x1080	264,062	21	0.656
	HOGOCB 9x9	10	8	45 1920x1080	264,062	19	0.485
	HOGOCB-RF 9x9	10	8	45 1920x1080	264,062	19.276 0.451

Acknowledgments

This work was supported by the Center of Integrated Smart Sensors funded by Ministry of Science, ICT & Future Planning as Global Frontier Project (CISS-2013M3A6A6073718).