Cédric Bourrasset

Luca Maggiani

Jocelyn Sérot

Franc ¸ois Berry

A Dataflow Object Detection System for FPGA-based Smart Camera

Embedded computer vision based smart systems raise challenging issues in many research fields, including real-time vision processing, communication protocols or distributed algorithms. The amount of data generated by cameras using high resolution image sensors requires powerful computing systems to be processed at digital video frame rates. Consequently, the design of efficient and flexible smart cameras, with on-board processing capabilities, has become a key issue for the expansion of smart vision systems relying on decentralized processing at the image sensor node level.

In this context, FPGA-based platforms, supporting massive data parallelism, offer large opportunities to match real-time processing constraints compared to platforms based on general purpose processors. In this paper, we describe the implementation, on such a platform, of a configurable object detection application, reformulated according to the dataflow model of computation. The application relies on the computation of the histogram of oriented gradients (HOG) and a linear SVM-based classification. It is described using the CAPH programming language, allowing efficient hardware descriptions to be generated automatically from high level dataflow specifications without prior knowledge of hardware description languages such as VHDL or Verilog. Results show that the performance of the generated code does not suffer from a significant overhead compared to handwritten HDL code.

I. INTRODUCTION

Traditional computer visions system often operate in a centralized manner, even for multi-camera applications, where the sequences of frames output by each camera are sent to a central computing unit. This central unit gathers information from all the available cameras and processes it in order to extract significant features. However as the number of source nodes increases, such a centralized approach quickly becomes infeasible because the central node becomes a bottleneck. This is specially true when high resolution cameras with high acquisition rates are deployed, for instance in object detection applications. In this context, and in the current state of network technology, the necessity to meet real-time processing constraints rules out any kind of centralized approach.

As a result, in the last years, many distributed video systems have been proposed. They aim at overcoming the above-mentioned bottleneck issue by distributing the computational intensive tasks on the camera nodes. Such nodes are generally called Smart Cameras (SC). Image processing capability is added by embedding processing units such as general purpose processors (GPP), specialized processors (DSP) or field programmable gate arrays (FPGA). The latter solution has drawn a lot of attention in the past years because it offers large opportunities for exploiting the fine grain, regular, parallelism that most of image processing applications exhibit at the lowest levels of processing. However, programming FPGA-based platforms is traditionally done using hardware description languages (HDLs) -see figure 1 -and therefore requires expertise in digital design. This, in practice, hinders the applicability of FPGA-based solutions.

As a response, a lot of work has been devoted in the past decade to the design and development of high-level languages and tools, aiming at allowing FPGAs to be used by programmers who are not experts in digital design, such as Catapult-C [START_REF] Graphics | Catapult c[END_REF], Stream-C [START_REF] Frigo | Evaluation of the streams-c c-to-fpga compiler: an applications perspective[END_REF] or Impulse-C [START_REF] Antola | A novel hardware/software codesign methodology based on dynamic reconfiguration with impulse c and codeveloper[END_REF]. Most of these tools propose a direct conversion of C or C++ code into HDL (VHDL or Verilog). While attractive, this approach suffers from several drawbacks. First, C programs often rely on features which are difficult, if not impossible, to implement in hardware (dynamic memory allocation for instance). This means that code frequently has to be rewritten to be accepted by the compilers. Practically, this rewriting cannot be carried out without understanding why certain constructs have to be avoided and how to replace them by "hardware-compatible" equivalents. So a minimum knowledge of hardware design principles is actually required. Second, C is intrinsically sequential whereas hardware is truly parallel. In the current state-of-the-art, this cannot be done in a fully automatic way and the programmer is required to put annotations (pragmas) in the code to help the compiler, which adds to the burden. Finally, the code generally has to undergo various optimizations and transformations before the actual HDL generation. With most of the existing tools these transformations and optimizations require inputs from the programmer [START_REF] Yankova | Automated hdl generation: Comparative evaluation[END_REF], who therefore must have a rather good knowledge in digital design. As a result, theres still a gap between what can be described with a general purpose, Turing-complete, language and what can be efficiently and automatically implemented on an FPGA.

In this context, there has been recently a regained attention on approaches relying on domain specific languages, such as Caltrop Actor language (CAL) [START_REF] Eker | Cal language report[END_REF]. The idea is that the aforementioned gap can be reduced by departing from the classical, sequential and imperative model of computation underpinning C or C++ formulations of algorithms. The dataflow model of computation, in particular, has nice properties which makes it a good candidate for harnessing the complexity of FPGA programming. This has been noticed by Najjar et al. in [START_REF] Najjar | Advances in the dataflow computational model[END_REF] who, in 1999, already argued that the two major characteristics of this model -all data are values and all operations are purely functional -nicely fit the execution model of FPGAs. A few years before, Sérot et al. had already demonstrated in [START_REF] Sérot | Functional programming on a dataflow architecture: Applications in real-time image processing[END_REF], [START_REF] Sérot | A visual dataflow programming environment for a real-time parallel vision machine[END_REF] that dataflow could be used to exploit massively parallel computers dedicated to real-time image processing. The key idea was to describe an application as a graph of dataflow operators and then physically map this graph on a network of data-driven processing elements (DDPs). But at the time of these experiments, the FPGA technology was still in its infancy and building a complete reconfigurable computing system required either resorting to GPPs or to ASICs .The dramatic improvements in FPGA technology during the past decade have provided an unique opportunity to bring this old idea up to date.

The main focus of this paper is to support this claim, in other words to show how a purely dataflow reformulation of an algorithm allows it to be implemented very efficiently on a FPGA without resorting either to low-level hardware description languages or complex and inefficient C-based HLS languages. The proposed approach relies on the CAPH [START_REF] Sérot | Caph: A language for implementing stream-processing applications on fpgas[END_REF]- [START_REF]The Caph Programming Language home page[END_REF] programming language, which is able to produce efficient FPGA designs from high level dataflow descriptions.

It will be demonstrated by describing the implementation, on a FPGA-based smart camera platform, of a real-time object detection application. This application, re-formulated here according to the dataflow Model of Computation (MoC), associates a feature extraction step (computation of histograms of oriented gradients, HOGs) and a linear classification step in order to predict the presence of predefined object (such as pedestrians or vehicles) in videos.

The remainder of the paper is organized as follows. The proposed application is presented in Sec. II and its dataflow reformulation is given in Sec. III. Sec. IV described the implementation, using the CAPH language obtained from this reformulation. Results are presented and discussed in Sec. V. Sec. VI concludes and gives perspectives for future work.

A. Feature Extraction

The descriptor extracted from each image is an Histogram of Oriented Gradients (HOG), computed by evaluating well-normalized local histograms of image gradient orientations in a dense grid. It has been shown in [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF] that this kind of descriptors provides excellent performances for visual object recognition. The computation of the HOG descriptors is sketched in Fig. 2. It consists in three steps.

The first step computes spatial derivatives G x and G y in x and y direction for each pixel (x, y) within image I. Gradient magnitude G(x, y) and angle θ(x, y) are then obtained as :

G(x, y) = G x (x, y) 2 + G y (x, y) 2
(1)

tan θ(x, y) = G y (x, y) G x (x, y) (2)
with G x (x, y) = ∂I ∂x and G y (x, y) = ∂I ∂y .

In the second step, the histogram of gradient directions is calculated by accumulating the gradient magnitude G(x, y) on a set of bins, where each bin covers a predefined segment of the full 0 . . . 180 o orientation range. Accumulation is carried out over local regions called cells (see Fig. 3).

In the third step, a local normalization of the histograms is performed for improving the descriptor invariance to illumination and contrast changes. It is here carried out by grouping cells into larger entities, called blocks, each block grouping 2 × 2 adjacent cells, and by normalizing each block separately.

For each position of the detection window, the final descriptor is built by concatenating the normalized histograms obtained on each block within the corresponding window1 .

It must be noticed that, with this approach, detection of objects in the image is carried out by shifting the detection window over the entire image and, for each position of the window, passing the descriptor computed on this window to the classifier. This so-called sliding detection technique has often been considered unpractical in a real-time execution context due to its heavy computing requirements, especially with high resolution images. In the sequel, we will show how its reformulation under the dataflow model of computation actually allows it to be implemented so that it can be computed on the fly, independently of the respective sizes of the input images and detection windows.

B. Classification

The classification stage (second module in Fig. 2) uses the descriptor produced by the previous stage to tell whether an object is present in the corresponding detection window. For this, a SVM-based (Support Vector Machine) algorithm is used. This algorithm compares the input descriptor with a reference model, produced by a supervised learning (training) step, as proposed by Vapnik et al. [START_REF] Vapnik | Estimation of Dependences Based on Empirical Data: Springer Series in Statistics[END_REF]. The training stepwhich is carried out offline -builds the reference model by assigning a great number of pre-defined examples More formally, given a set of l data elements x 1 , ..., x l and their corresponding classes y 1 = y(x 1 ), ..., y l = (x l ) where x i ∈ R n and y i = ±1, the classification function can be expressed as follows:

y(x) = sgn N SV i=1 y i α i K(x i , x) + b , 0 ≤ α i ≤ C (3)
where K(x i , x) is a kernel function, C is a regularization constant, α i and b are parameters given by the learning phase. N SV is the number of the reference features, called Support Vectors (SVs). In our case x 1 , ..., x l are database images and y correspond to the presence or not of the targeted objects in images. When linear kernels are used for binary classification, the classification function can be expressed as a simple dot product [START_REF] Cortes | Support-vector networks[END_REF] :

y(x) = w T • x + b (4)
The weight vector w and the bias b are determined by the training phase for each object we want to detect.

C. Algorithm

The algorithm for the object detection application, detailing feature extraction and the classification step introduced in the previous section, is given in listing 1, in pseudo code.

The first step (labeled HOG) corresponds to the feature extraction described in Sec. II-A. It computes the HOG descriptor for each cell in the source image. The magnitude and the orientation angle of the gradient are computed for every pixel using the pixel-wise operations gradx, grady, square root and arctan. Then, the angle is discretized over eight uniformly spaced bins 2 . In listing 1, this discretization is performed by the function findbin. The function getcell returns the cell to which the current pixel belongs. Finally, for each cell, the descriptor is computed by first grouping cells in blocks and normalizing each histogram on the grouped cells using statistics computed on the block (functions createblock and norm).

The second step (labeled SVM) corresponds to the classification described in Sec. II-B. For each position of the detection window, the descriptors computed on the enclosed cells are concatenated (function gatherHOG) to build a global descriptor and this descriptor is passed to the classification function svm, which computes the dot product described by equation 4 and outputs the classification result for this window (object present or not). § ¤ // HOG f o r a l l p i x e l ( i , j ) i n image I g r a d x ( i , j ) = I ( i , j + 1 ) -I ( i , j -1) g r a d y ( i , j ) = I ( i +1 , j ) -I ( i -1, j ) m a g n i t u d e = gradx 2 + grady 2 a n g l e = a r c t a n ( g r a d y ( i , j ) , g r a d x ( i , j ) )

// find the histogram bin for this orientation b i n = f i n d b i n ( a n g l e )

// find the cell to which the current pixel belongs c e l l = g e t c e l l ( i ,

III. DATAFLOW REFORMULATION

In this section, we will reformulate the algorithm described in Sec. II according to a dataflow model of computation (MoC). This reformulation will be the key for its efficient implementation on a FPGA, as demonstrated in Sec. IV.

The dataflow MoC we use is the one initially introduced by Dennis in [START_REF] Dennis | Data flow supercomputers[END_REF] : applications are described as a collection of computing units (called actors) exchanging streams of tokens through unidirectional FIFO-like channels. Execution occurs as tokens litteraly flow through channels, into and out of actors, according to a set of firing rules. These firing rules specify that an actor becomes active whenever tokens are available on all of its input channels and token(s) can be written on its output channel(s). When this occurs, input tokens are consumed, and result(s) are computed and produced on the output channel(s).

We extend the original model with a mechanism allowing structured values, such as images, windows or histograms, to be represented as sequential streams of tokens. With this mechanism, the different operations involved in a given algorithm can be described as actors operating "on the fly" on the corresponding streams. For this, we will actually distinguish two categories of tokens : data tokens and control tokens. Data tokens will be carrying values (such as pixels, or histogram values). Control tokens will be used to structure the streams. This is illustrated in Fig. 4 with an actor computing the horizontal derivative of images. For each pixel P (i, j) of the input image, the corresponding pixel in the output image is either P (i, j) -P (i, j -1) (for j > 0) or P (i, j) (for j = 0). Each image is represented as a list of lists, the control token "<" (resp. ">") denoting the start (resp. end) of a list 3 . For legibility, the size of the images is 3 × 3 in Fig. 4. The behavior of the DX actor is purely data driven : whenever a token is available on its input, it is consumed and a corresponding result token is produced on the input. Informally, this behavior can be specified as follows 4 :

• when waiting for a new image and reading a "<" control token, write the same token on output and start waiting for a new line, • when waiting for a new line and reading a "<" control token, write the same token on output, set local variable z to 0 and start waiting for pixels, • when waiting for pixels and reading a data token p, write data token p-z and set variable z to p,

• when waiting for pixel and reading a ">" control token, write the same token on output and start waiting for a new line, • when waiting for a new line and reading a ">" control token, write the same token on output and start waiting for a new image. Note that this style of description naturally supports a pipelined execution scheme; processing of a line, for example, can start as soon as the first pixel is read without having to wait for the entire structure to be received; this feature, which effectively allows concurrent circulation of successive "waves" of tokens through the network of actors is of course crucial for on-the-fly processing. In the rest of this section, we propose a complete reformulation of the algorithm described in Sec. II according the dataflow model described above, starting with a dataflow graph showing all involved actors and data dependencies between these actors and continuing with a description of the behaviour of the most significant actors.

The complete dataflow graph of the algorithm listed in listing 1, reformulated according to our dataflow model, is given in Fig. 5. In this figure, each gray box correspond to an actor and channels are drawn as black arrows connecting theses boxes. Images enter the graph as structured streams of pixels and results are output as binary images (also represented as structured stream of pixels) indicating whether object has been detected at each position of the source image.

All definitions and notations in the sequel refer to those used in Fig. 5.

A. Feature extraction

This part corresponds to the upper part of the graph (outlined in a red box in Fig. 5).

Gradient Computation

Gradient computation is a classical image processing operation. However, when targeting FPGAs, the main challenge is the implementation of the square root and arctan functions. The square root is often approximated as the sum of the absolute values of the gradient components but the computation of the arctan function is more tricky. Classical solutions based on look-up tables (LUTs), such as described in [START_REF] Lee | Accelerating histograms of oriented gradients descriptor extraction for pedestrian recognition[END_REF] for example, either requires large amounts of memory or multi-cycle operations which significantly reduces data throughput. Several approaches, such as [START_REF] Bauer | Fpga-gpu architecture for kernel svm pedestrian detection[END_REF], [START_REF] Hahnle | Fpga-based real-time pedestrian detection on high-resolution images[END_REF], have proposed to rely on the binning strategy to accumulate the histogram without explicitly computing arctan(G y /G x ) but their sequential formulation does not fit well with the dataflow model of computation.

We propose to use a set of eight 3×3 convolution kernels C 0...7 not to directly bin the gradient orientation but instead to calculate the contribution of each corresponding direction to each histogram bin. With this approach, the components of the final histogram can be computed in parallel.

For this, a set of eight actors conv, each parametrised by a 3 × 3 kernel C k , each accepts an image p and produces another image q in which non-null pixels are those which have to be accumulated in the k th bin of the target histogram.

More formally, given an n × m image p, encoded as a structured streams of pixel

p =<< p 1,1 . . . p 1,m > . . . < p n,1 . . . p n,m >> (5)
the behavior of actor conv, parametrised by kernel C k , can defined in a purely functional manner with the following equation :

conv C k (<< p 1,1 . . . p 1,m > . . . < p n,1 . . . p n,m >>) = << q 1,1 . . . q 1,m > . . . < q n,1 . . . q n,m >> HOG Extraction SVM Model Pixels (p) Serializer Norm Factor L1norm conv 0 q 0 abs 0 r 0 xsum 0 s 0 ysum 0 h 0 block 0 conv 1 q 1 abs 1 r 1 xsum 1 s 1 ysum 1 h 1 block 1 conv 2 q 2 abs 2 r
q i,j = 0, if i ∈ {1, n} ∨ j ∈ {1, m} cos θ k p i,j+1 -cos θ k p i,j-1 + sin θ k p i+1,j -sin θ k p i-1,j , otherwise and
θ k = kπ 8 , k ∈ {0, . . . , 7} 2

Histogram Computation

Histogram computation is the major processing bottleneck of all HOG-based detection applications and this is the reason why HOG descriptors has rarely been used (even when improved by Zhu et al. [START_REF] Zhu | Fast human detection using a cascade of histograms of oriented gradients[END_REF]). In [START_REF] Porikli | Integral histogram: A fast way to extract histograms in cartesian spaces[END_REF],

Porikli proposed to use so-called integral histograms to speed-up histogram computation. The technique allows fast evaluation of histogram values within rectangular regions regardless of their size. However, in our case, it would require to first generate an integral histogram for each histogram bin, and then compute the histograms of the target regions by intersection, which is not easily formulated under the dataflow MoC.

We propose, rather, to compute the k th histogram entry by simply accumulating gradient magnitudes over each cell using two successive actors : one summing values in in the x direction and the other in the y direction. These actors are named xsum and ysum in Fig. 5. On each bin channel k, they compute an histogram image h k defined as

∀(ii, jj), h k (ii, jj) = jj•d j=(jj-1)•d+1 ii•c i=(ii-1)•c+1 |q k (i, j)| (6)
where q k is the k th bin image produced by corresponding conv actor and (ii, jj) corresponds to the cell coordinates, given by ii = {1, 2, ..., n c } and jj = {1, 2, ..., m d } (where n × m is the input image size). In other words, the histogram component corresponding to the k th bin is given by

h k = ysum(xsum(abs(q k ))) (7)
where the three actors abs, xsum and ysum can be defined as follows.

The abs actor simply computes the absolute values of its input image :

abs(<< q 1,1 . . . q 1,m > . . . < q n,1 . . . q n,m >>) = << r 1,1 . . .

B. Normalization

As illustrated in Fig. 3, the HOG descriptor of a given cell is obtained by gathering the histograms computed on a 2 × 2 neighbourhood. This means that each descriptor will have 32 components (eight bins × four neighboors).

Extraction of the 2 × 2 neighbourhood extraction is performed on each bin in parallel by the block actor. This actor takes one stream hk (representing the input image) and produces four streams z 4k , z 4k+1 , z 4k+2 , z 4k+3 . If the input stream describes an image with p lines of s pixels, each output stream will describe one neighboring image (with p -1 lines of s -1 pixels). I.e. :

block(hk) = (z 4k , z 4k+1 , z 4k+2 , z 4k+3 ) (11)
where z 4k =<< hk 1,1 , . . . , hk 1,s-1 > . . . < hk p-1,1 , . . . , hk p-1,s-1 >> z 4k+1 =<< hk 1,2 , . . . , hk 1,s > . . . < hk p-1,2 , . . . , hk p-1,s >> z 4k+2 =<< hk 2,1 , . . . , hk 2,s-1 > . . . < hk p,1 , . . . , hk p,s-1 >> z 4k+3 =<< hk 2,2 , . . . , hk 2,s > . . . < hk p,2 , . . . , hk p,s >> In the previous definition, if we consider the first element of each stream z i , the four tokens represent the neighbourhood of the current histogram location (hk 1,1 , hk 1,2 , hk 2,1 , hk 2,2 ). Applied to each bin image, the block actor then generates 32 parallel streams, each stream carrying each one a descriptor component (z 0 , ..., z 31 ). Each z i stream is a HOG component stream of x, y tokens where respectively x = n/d -1 and y = m/c -1 (n,m in the image input size and c,d is the histogram cell size). A HOG component stream z i is represented as: z i =<< z 1,1 , . . . , z 1,y > . . . < z x,1 , . . . , z x,y >>

For each cell, the normalization of the descriptor (z 0 , ..., z 31 ) is operated by two actors : the norm_factor actor computes the normalization factor ||z|| for each cell (as defined in Eq. 13) and the L1norm actors performs the normalization itself (as defined in Eq. 15).

The norm_factor actor can be defined as follows:

norm f actor(z 0 , ..., z 31 ) = ||z|| (13)
where

||z|| =<< z 1,1 , ..., z 1,y > ... < z x,1 , ..., z x,y >> and
z i,j = 31 i=0 zi i,j
Before computing the normalization of each descriptor component, we first concatenate the 32 streams (z 0 , ..., z 31 ) into a single stream zs (in figure 5). This serialisation reduces the number of L1norm actors from 32 to 1 limiting the hardware resources in implementation. The serialiser produces a s× t image stream where s = x and t = 32 × y and can be defined as: serialiser(z 0 , ..., z 31 32 streams ) = zs 1 stream [START_REF] Cortes | Support-vector networks[END_REF] where zs =<< zs 1,1 , ..., zs 1,t > ... < zs s,1 , ..., zs s,t >> The full block descriptor normalization is performed by the L1norm actor which divides the serialized HOG descriptor stream zs by the norm factor (for each cell) . The L1norm actor can be defined by: L1norm(<< zs 1,1 , ..., zs 1,t > ... < zs s,1 , ..., zs s,t >>, << z 1,1 , ..., z 1,y > ... < z x,1 , ..., z x,y >>) = x (15) where

x =<< x 1,1 , ..., x 1,t > ... < x s,1 , ..., x s,t >> and x i,j = zs i,j /z i,jj , jj = j/32

We now define the higher-order function norm corresponding to the normalization of HOG. For the tuple (h 0 , ..., h 7 ) coming from the histogram function, the norm function produce the HOG stream (x). norm(h 0 , ..., h 7 ) = L1 norm ( serialiser (z 0 , ..., z 31 ), normf actor (z 0 , ..., z 31 )) [START_REF] Lee | Accelerating histograms of oriented gradients descriptor extraction for pedestrian recognition[END_REF] where the tuple (z 0 , ..., z 31 ) is obtained by applying the block actor to each histogram stream (h 0 , ..., h 7 ). Now we have defined all actors or functions for the HOG extraction, we can simply express the relation between the input stream p with the output descriptor stream x. This function is a composition of the previous ones:

x = hog(p) = norm(hists(convs(p))) (17)
where hists and convs are respectively the hist function and conv actor applied to all parallel bins.

C. Classification

To evaluate the SVM results over a detection window, we need to compute the dot product of all histogram blocks belonging to it using a pre-trained model. According to the linearity of the equation 4, we can compute partial dot products to obtain the final result. The corresponding computation is described using four actors, all shown in the lower part of Fig. 5 : weight_distribution, dot_product, windowing and bias. The SVM-based classification step can be defined by the following equation :

svm w,n,m,b (x) = bias (windowing (dot (x, weight distribution (x, w, n, m)), n, m) b) ( 18
)
where x is the input stream of HOG descriptors, w the weight vector obtained by the external training phase, n and m the sizes of the detection window size and b the bias.

The weight_distribution actor generated the partial weight vector w corresponding to the partial descriptor x. More precisely, given the structured stream x, it produces a synchronised stream of weights (from an external memory) as function of the pre-trained model and the detection window size (n, m). Considering the serialized input descriptor flow x (output of the hog extraction part) of a size s, t, the actor is then expressed as follows:

weight distribution(x, w, n, m) =<< w 1,1 , ..., w 1,t >, ..., < w s,1 , ..., w s,t >> (19)
Once the weight w has been generated, the dot product actor computes the projection of w over the current x as in equation 20.

dot(x, w)

=<< d 1,1 , ..., d 1,t >, ..., < d s,1 , ..., d s,t >> (20)
where

d i,j = x i,j • w i,j
The projection values are then processed by the windowing actor. It accumulates the results according to the window which the cell is belonging. The windowing actor is a composition of the two previous actors xsum and ysum presented in the section III-A2 with a configurable detection window size n, m (sketched on figure 5).

windowing(<< d 1,1 , ..., d 1,t >, ..., < d s,1 , ..., d s,t >>, n, m) =<< f 1,1 , . . . , f 1,l > . . . < f k,1 , . . . , f k,l >> (21) where

f ii,jj = jj•m j=(jj-1)•m+1 ii•n i=(ii-1)•n+1 d ij
Finally, the actor bias adds the b parameter as expected by the SVM model. The detection result y is then expressed in equation 22.

bias(<< f 1,1 , . . . , f 1,l > . . . < f k,1 , . . . , f k,l >>, b) =<< y 1,1 , ..., y 1,l >, ..., < y k,1 , ..., y k,l >> [START_REF] Joachims | Svmlight: Support vector machine[END_REF] where

y i,j = 0 if f i,j < b 1 otherwise
This completes the dataflow reformulation of the object detection algorithm. In the next section, this formulation will be turned into a concrete program to be implemented on a FPGA platform.

IV. IMPLEMENTATION In this section, we describe a concrete implementation of the object detection application inspired from the dataflow formulation proposed in previous section. It is carried out using the CAPH dataflow programming language. A brief presentation of this language is first given in Sec. IV-A. Then the actual encoding of the application in CAPH is described in Sec.IV-B.

A. The CAPH language

CAPH [9]- [START_REF]The Caph Programming Language home page[END_REF] is a high-level, domain specific language (DSL) based upon the dataflow model of computation. Its main goal is to provide a fully-automated compilation path from high-level dataflow descriptions of algorithms to their implementations on FPGA-based platforms, with a specific focus on stream processing applications. For such applications, the CAPH toolchain provides an effective rapid prototyping environment for FPGA programming, producing ready-to-synthetize RT-level VHDL code.

The CAPH language embodies the dataflow model by providing two formalisms : one for describing the behavior of actors operating on structured streams of values and another for describing the structure of dataflow graphs built from such actors.

Following the principles introduced in Sec. III, the behavior of actors in CAPH is expressed as a set of transition rules. Each rule describes what happens (in terms of computation and/or I/O) whenever a new token (or set of tokens) is available on the input(s). It consists of a set of patterns, involving inputs and/or local variables and a set of expressions, describing modifications of outputs and/or local variables.

The actor sub-language of CAPH has already been described in previous papers [START_REF] Sérot | Caph: A language for implementing stream-processing applications on fpgas[END_REF]- [START_REF]The Caph Programming Language home page[END_REF] ( [START_REF] Sérot | High-level dataflow programming for real-time image processing on smart cameras[END_REF], in particular, describes a preliminary CAPH implementation of the HOG algorithm) and will not discussed further in this paper. Description of dataflow graphs (DFGs) in CAPH is carried out using a textual network description language (NDL). This NDL is a small, higher-order, purely functional language in which DFGs are described by defining and applying wiring functions. A wiring function is a function accepting and returning wires (graph edges). This concept is illustrated in Fig. 6, where the DFG on the left is described by the CAPH program on the right. Here, two wiring functions are defined : neigh13 and neigh33. The former takes a wire and produces a bundle of three wires representing the 1 × 3 neighborhood of the input stream, by applying twice the built-in actor dp (one-pixel delay). The latter takes a wire and produces a bundle of nine wires Fig. 6: Graph description with wiring functions in CAPH representing the 3 × 3 neighborhood of the input stream, by applying the previously defined neigh13 function and the built-in dl actor (one-line delay) 5 .

The main originality of the CAPH NDL is to allow the definition of graph patterns as polymorphic, higher-order wiring functions, which greatly eases the description of large and complex graphs. This aspect has proven to be of significant importance for our object detection application, as will be evidenced in the next section.

B. The object detection application in CAPH

In Sec. III, the CAPH dataflow formulation of the object detection application is given. Since a prototype version of this implementation has already been described in [START_REF] Sérot | High-level dataflow programming for real-time image processing on smart cameras[END_REF], we will focus here on the higher-order capabilities of the language. These features have not been described hitherto and we will try to demonstrate how they greatly ease the description of the application.

The toplevel description of the application is shown in listing 2. The corresponding dataflow graph (generated by the compiler) is shown in Fig. 7. Input and output are introduced by the stream keyword. They respectively correspond here to the sequence of 8-bit images produced by the camera (each image beeing encoded as a structured stream of pixels) and to the sequence of binary images showing detection results (each image being also encoded as a structured stream of pixels). Parameters -the complete set of weights w for the classification step, the dimensions n and w of the detection window and the bias factor b -are communicated by means of asynchronous ports 6 .

Distinction between data and control tokens is achieved by using a so-called variant type (dc) for input and output. The type dc is a polymorphic algebraic data type which can defined as

type t dc = SoS | EoS | Data of t
where SoS (Start of Structure), EoS (End of Structure) and Data are value constructors encoding respectively the "<" and ">" control tokens and data tokens. The t parameter denotes a type variable 7 . § ¤ The algorithm itself is encoded using several wiring functions8 : convs, hists, hog, norm and svm. Each of these functions corresponds to a step of the algorithm described in the previous sections (in particular, the hog and svm functions directly correspond to the feature extraction and classification steps). For legibility, the code of the actors (conv_33, xsum, ysum, abs, block_extraction, norm_factor, serializer and l1_norm) has not been reproduced here.

The convs function (lines 1-3) creates the eight parallel streams representing the images q k by instanciating the convolution actor conv_33 with eight distinct kernels (stored a 2D array constant coeff, not shown here). For this, it uses the mapi builtin higher-order wiring function, which can be defined as

mapi f (x 1 , . . . , x n ) = (f 0 x 1 , . . . , f (n -1) x n )
In our case, the tuple on which the mapi is applied is generated by the rep actor. This simply generates n multiple copies of its input stream (n = 8 here).

The hists function (lines 5-7) generates the images representing the eight histogram bins. The abs actor computes the absolute value of the input stream coming from the convolution stage. The xsum and ysum actors are accumulators where the number of iterations is specified by the xs and ys parameters respectively. Replication of the processing on the eight parallel streams corresponding the different bins is expressed using the map builtin higher-order wiring function, whose functional definition is :

map f (x 1 , . . . , x n ) = (f x 1 , . . . , f x n )
The map function is here applied to the locally defined function hist, which expresses the computation of the histogram on a single bin. Its definition (line 6) is the direct translation of Eq. 7.

The definition of the hog function is a direct translation of Eq. 17 : it is a composition of the functions convs, hists and norm. The first two arguments (xs and ys) give the histogram cell size (set to 8 here when the hog function is called, line 20).

The norm function (lines 11-15) is also a direct translation of Eq. 16, combining actors block_extraction, norm_factor, serializing and l1_norm. The map higher-order function takes here as input the tuple (h0, ..., h7) which corresponds to the outputs of the histogram step as H 0 to H 7 in figure 5.

The svm function (lines 17-18) implements the classification step. It operates on the serial descriptor produced by hog function. It is, again, a direct translation of Eq. 18.

Finally, the function describing the global application (line 20) is obtained by composing the hog and svm functions.

C. Platform

In this section, we present our FPGA-based smart camera platform, the DREAMCAM [START_REF] Birem | Dreamcam : A modular fpga-based smart camera architecture[END_REF]. For the object detection application discussed here, the architecture of the DREAMCAM can be described as a combination of three modules as depicted in Fig. 8. The first module -which is actually application-independantmanages the external CMOS camera interfaces, generating the structured pixel streams for the following modules. The second module is the one which is actually generated by the CAPH compiler from the code described in the previous section. It implements the dataflow graph depicted in Fig. 7. The third module interprets results generated by the application for visualization (to produce images like illustrated in Fig. 9b). It is implemented using an embedded softcore microprocessor which actually acts as a system controller and manager. Moreover, since the pre-trained object model (w,n,m,b ports in listing 2) are inputs of the processing, the softcore has the ability to update these values, changing the object targeted in the camera stream. V. RESULTS In this section, we discuss the results obtained by deploying the VHDL code produced by the CAPH compiler on our FPGA-based smart camera. We first present the actual classification results, obtained on real image sequences, in order to assess the correctness of the implementation. Then the efficiency of the implementation is evaluated, by comparing some performance indicators with those obtained with other, state-of-the-art implementations.

Classification results

The proposed detection system has been firstly benchmarked to detect pedestrians on image. The classifier model has been obtained by a training phase with the INRIA dataset with the SVMlight tool [START_REF] Joachims | Svmlight: Support vector machine[END_REF]. In figure 9a the impact of the HOG dataflow reformulation over the classifier detection is shown. To evaluate the classifier performance, the test results are expressed with the Receiver Operating Characteristics (ROC) metric, where the True Positive Ratio (TPR) is plotted as function of the False Positive Ratio (FPS). For comparison, in figure 9a the OpenCV HOG implementation, based on Dalal algorithm [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF], has been evaluated with respect to ours.

Even though our detection system is using fixed-point arithmetic -compared to the floating point OpenCV implementation -it is showing only a slight performance decrease (up to 3% at 3.3% FPR). Over the INRIA pedestrian dataset [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF], our dataflow reformulation achieves 90% TPR and 3.3% FPR at 50 fps while the hardware reference implementation [START_REF] Hahnle | Fpga-based real-time pedestrian detection on high-resolution images[END_REF] provides 2% higher TPR (92% TPR at 3.3% FPR). Moreover, it delivers comparable results with those obtained with a full-fledged floating point implementation, while offering a path for FPGA friendly hardware implementations. In figure 9b an example of pedestrian detection is shown. The original picture has been taken form the Daimler dataset [START_REF] Enzweiler | Monocular pedestrian detection: Survey and experiments[END_REF] and processed with our dataflow system with the same training model as above.

Performance results

Deployment is performed using Quartus II 13.1 synthesis toolchain for synthetizing the VHDL code generated by the CAPH compiler. Two indicators are used to assess performances : resource usage and number of processed frames per second (FPS).

Table I gives resource usage on the Altera Cyclone III EP3C120 embedded on the DREAMCAM platform for a 1280×1024 image resolution, expressed as in terms of used logic elements (LEs), memory bits and embedded multipliers, for each step of the algorithm. When a given step involves several distinct actors (e.g., gradient) results are given for each involved actor.

The whole dataflow implementation requires 16392 LEs (around 17% of the target FPGA) and 70 kbits of embedded memory cells. Only one DSP module is used, for computing the dot product in the SVM prediction step 9 .

A significant part of the logic elements are used to implement the FIFO channels used to exchange tokens between actors. The width and depth of these FIFOs is computed by the CAPH compiler . These FIFOs are inherent to our dataflow model of execution. In table II our implementation is compared, both in terms of resource usage and maximum FPS, with those reported by three other authors on several FPGA plaforms. Since LE count is highly device dependent, comparison of resource usage is carried out in terms of LUTs and registers. For this, the LE reported in table I are first split in two : those implementing LUTs and those implementing registers.

Our implementation, obtained without writing a single line of HDL code, offers performances which are comparable in terms of resource usage and FPS. Mizuno's [START_REF] Mizuno | Architectural study of hog feature extraction processor for real-time object detection[END_REF] and Hahnle's [START_REF] Hahnle | Fpga-based real-time pedestrian detection on high-resolution images[END_REF] implementation use a hand-crafted HDL optimized pipeline to boost up performances. In particular, compared to Mizuno [START_REF] Mizuno | Architectural study of hog feature extraction processor for real-time object detection[END_REF] we significantly reduce the LUTs and registers footprint without sacrifying throughput (fps × resolution). Compared to Hahnle [START_REF] Hahnle | Fpga-based real-time pedestrian detection on high-resolution images[END_REF], our implementation requires more logic resources but need less internal memory (70 kbits out of 936 kbits for the HOG extraction). Compared to Kadota [START_REF] Kadota | Hardware architecture for hog feature extraction[END_REF], our implementation performs better in terms of FPS, but uses more LUTs and registers, due to the increased image resolution.

Fig. 1 :

 1 Fig. 1: Hardware design methods

Fig. 2 :

 2 Fig. 2: Overview of the object detection application

8 pxFig. 3 :

 83 Fig. 3: Illustration of detection window, block and cell

  j ) h i s t o g r a m ( c e l l , b i n ) = h i s t o g r a m ( c e l l , b i n ) + m a g n i t u d e end f o r a l l c e l l s c i n image I // gather cells into block d e s c r i p t o r ( c ) = c r e a t e b l o c k ( h i s t o g r a m ) d e s c r i p t o r ( c ) = norm ( d e s c r i p t o r ( c ) ) end // SVM f o r a l l d e t e c t i o n windows w i n image I f i n a l d e s c = gatherHOG ( d e s c r i p t o r , w ) y = svm ( f i n a l d e s c , model ) end ¦ ¥ Listing 1: Algorithm

<< 0 1 2 Fig. 4 :

 24 Fig. 4: Dataflow processing example

Fig. 5 :

 5 Fig. 5: Dataflow graph of the object detection application

  r 1,m > . . . < r n,1 . . . r n,m >>[START_REF] Sérot | A visual dataflow programming environment for a real-time parallel vision machine[END_REF] where r i,j = |q i,j |The xsum actor accumulates pixels in the x (row) direction. On each line of the input image, it reads c consecutive values and writes the sum of these values. Formally :xsum(<< r 1,1 , . . . , r 1,m m elements > . . . < r n,1 , . . . , r n,m >>) =<< x 1,1 , . . . , x 1,s s = m/d elements > . . . < x n,1 , . . . , x n,s >>The ysum operates as xsum but in the y direction. On each column of the input image, it reads d consecutive values and writes the sum of these values. Formally :ysum(< < x 1,1 , . . . , x 1,s > . . . < x n,1 , . . . , x n,s > n lines >) =< < h 1,1 , . . . ,h 1,s > . . . < h p,1 , . . . , h p,s > p = n/c lines > The composition of actors xsum and ysum, on a n × m input image produces a n/c × m/d output image. In our case, c × d is the cell size (c = d = 8).

Fig. 7 :

 7 Fig. 7: Dataflow graph for the HOGSVM application from the code in listing 2

Fig. 8 :Fig. 9 :

 89 Fig. 8: Architecture of the object detection application as implemented on the DREAMCAM platform

  0 .. z 3 z 4 .. z 7 z 8 .. z 11 z 12 .. z 15 z 16 .. z 19 z 20 .. z 23 z 24 .. z 27 z 28 .. z 31

		conv 3	conv 4	conv 5	conv 6	conv 7
		q 3	q 4	q 5	q 6	q 7
		abs 3	abs 4	abs 5	abs 6	abs 7
	2	r 3	r 4	r 5	r 6	r 7
	xsum 2	xsum 3	xsum 4	xsum 5	xsum 6	xsum 7
	s 2	s 3	s 4	s 5	s 6	s 7
	ysum 2	ysum 3	ysum 4	ysum 5	ysum 6	ysum 7
	h 2	h 3	h 4	h 5	h 6	h 7
	block 2	block 3	block 4	block 5	block 6	block 7
		32 flows	/

z

TABLE I :

 I Hardware resource usage level for 1280×1024 image resolutionDespite the overhead induced by the FIFO channels, the hardware occupancy performance are comparable with state of the art systems.

	Operation	Actors	Logic elements (LE)	Memory (kbits)	DSP
	Gradient	rep8 8 × conv 33	20 1036	0 25.7	0 0
		8 × abs	238	0	0
	Histogram	8 × xsum	744	0	0
		8 × ysum	981	20.8	0
		8 × block extraction	2283	23.7	0
	Normalization	serializer norm factor	829 161	0 0	0 0
		L1norm	320	0	0
		weight distr	51	0	0
		dot prod	29	0	1
	SVM prediction	xwin	240	0	0
		ywin	130	1	0
		decision	10	0	0
	Channels Fifo		9320	0	0
	Total		16392 LE (17%)	70 kbit (2%)	1/576 DSP

The size of the detection window is supposed to be a multiple of the size of the block.

Since spatial information are often unrelated to vertical orientations, only the upper semi-circumference is considered regardless of the full turn[START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF]

In Fig.

[START_REF] Yankova | Automated hdl generation: Comparative evaluation[END_REF], the input of output sequences of tokens should be read from left to right; in other words, the input (resp. output) tokens are fed (resp. produced) to (resp. by) the actor in this order : first "<", then "<", then 0, then 1, etc. (resp. "<", "<", 0, 1, etc.).[START_REF] Yankova | Automated hdl generation: Comparative evaluation[END_REF] Formally, and as described in the next section, the CAPH language encodes this behavior as a set of transition rules, where each rule is described as a combination of pattern matching on the input(s) and local variable(s) and of actions on the output(s).

The (sub)graphs resulting from the application of the neigh13 and neigh33 wiring functions are delineated using boxes drawn with short and long dash, respectively, on the figure.

Asynchronous ports provide a means to modify application parameters without having to reload the whole application on the target FPGA.

The type system of CAPH is similar to thoses equiping modern functional programming languages such as Haskell or ML. It supports parametric polymorphism and higher-order functions, in particular.

In CAPH, as in most of functional programming languages, function application is denoted without parenthesis, so that f xy means (here) f (x, y).

For gradient computation, no DSP is used since all the required multiplications involve only constant factors.

ACKNOWLEDGMENT

This work has been sponsored by the French government research programme "Investissements d'avenir" through the IMobS3 Laboratory of Excellence (ANR-10-LABX-16-01), by the European Union through the program Regional competitiveness and employment 2007-2013 (ERDF Auvergne region), and by the Auvergne region.

VI. CONCLUSION AND FUTURE WORK We have described the application of a real-time object detection application on a FPGA-based smart camera architecture.For this application, we have shown that an efficient implementation can be obtained with a dataflow based language whose abstraction level is significantly higher than that of traditional HDL languages such as VHDL or Verilog. Together with previous experimentations [START_REF] Sérot | High-level dataflow programming for real-time image processing on smart cameras[END_REF], [START_REF] Sérot | Implementing stream-processing applications on fpgas: A dsl-based approach[END_REF], this confirms that, for applications having to operate on the fly on video data streams, the dataflow model of computation, used jointly as a programming model and an execution model can offer a very effective way to conciliate abstraction and efficiency when programming FPGAs. This in turn opens significant opportunities to exploit this kind of devices in architectures such as smart cameras, since, in the mid and long term, it is not realistic to require that programmers of these architectures rely on low-level hardware description languages.

We intend to continue working in several directions in order to support this claim. First, for the discussed application, by assessing several alternative formulations and generalisations. For example, using overlapping detection windows to improve detection reliability in complex scenes or merging multi-scale SVM outputs to go towards a neuro-inspired classification scheme. Second, in reformulating and implementing other applications. Third, in improving the CAPH compiler, by optimizing the code generated by VHDL backend in order to minimize resource usage or reduce critical paths.