Olivier Kihl
email: olivier.kihl@ensea.fr

David Picard
email: picard@ensea.fr

Philippe-Henri Gosselin
email: philippe-henri.gosselin@ensea.fr

A Unified framework for local visual descriptors

Keywords: Image Processing and Computer Vision, Vision and Scene Understanding, Video analysis, Image/video retrieval retrieval, Object recognition, Feature representation

Local descriptors are the ground layer of recognition feature based systems for still images and video. We propose a new framework to explain local descriptors. This framework is based on the descriptors decomposition in three levels: primitive extraction, primitive coding and code aggregation. With this framework, we are able to explain most of the popular descriptors in the literature such as HOG, HOF, SURF. We propose two new projection methods based on approximation with oscillating functions basis (sinus and Legendre polynomials). Using our framework, we are able to extend usual descriptors by changing the code aggregation or adding new primitive coding method. The experiments are carried out on images (VOC 2007) and videos datasets (KTH, Hollywood2 and UCF11), and achieve equal or better performances than the literature.

Introduction

Most multimedia retrieval systems compare multimedia documents (image or video) thanks to three main stages: extract a set of local visual descriptors from the multimedia document; learn a mapping of the set of descriptors into a single vector to obtain a signature; compute the similarity between signatures. In this paper, we focus on the computation of visual descriptors. The main goal of local visual descriptors is to extract local properties of the signal. These properties are chosen to represent discriminative characteristic atoms of images or videos. Since local descriptors are the ground layer of recognition systems, efficient descriptors are necessary to achieve good accuracies. Such descriptors have become essential tools in still image classification [START_REF] Everingham | The PASCAL Visual Object Classes Challenge[END_REF][START_REF] Chatfield | The devil is in the details: an evaluation of recent feature encoding methods[END_REF] and video action classification [START_REF] Wang | Action recognition by dense trajectories[END_REF][START_REF] Laptev | Learning realistic human actions from movies[END_REF][START_REF] Schuldt | Recognizing human actions: A local svm approach[END_REF].

The main contribution of this paper is a unified framework for visual descriptors that includes all the usual descriptors from the literature such as SIFT (Scale-invariant feature transform) [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF], SURF (Speeded Up Robust Features) [START_REF] Bay | Surf: Speeded up robust features[END_REF], HOG (Histogram of Oriented Gradient) [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF], HOF (Histogram of Oriented Flow) and MBH (Motion Boundary Histogram) [START_REF] Dalal | Human detection using oriented histograms of flow and appearance[END_REF]. This framework is based on the decomposition of the descriptor in three levels: primitive extraction, primitive coding and code aggregation. Each popular descriptor is composed by a given primitive, a given coding and a given aggregation. Moreover, our framework allows to extend every descriptor by changing one or more of the three levels, e.g. changing the primitive level of HOG (gradient) by the motion primitive produces the HOF descriptor. The second contribution of this paper is the proposal of new coding and aggregation steps, the later being based on oscillating functions (Sinus and Polynomials), leading to new descriptors. Finally, we propose an exploration of the possible combinations of these primitives, coding and aggregation methods provided by the framework, that allows us to design more efficient and complementary descriptors.

The paper is organized as follows. In section 2, we present the most popular descriptors in the literature, for still images and for human action videos. We also present the most common approaches to compute the signature of a multimedia document from a set of descriptors. Then, in section 3, we present our framework, explain the most popular descriptors, and extend them by modifying some of these three steps. Finally, in section 4, we carry out experiments on one still image classification dataset and three action classification datasets for several descriptors and combinations of them.

Related work

In this section, we present the most popular descriptors in the literature, first for still image and then for human action video. We also present the most common approaches to compute the signature of a multimedia document from a set of descriptors.

Still image descriptors

In the past ten years, several descriptors have been proposed for key-points matching and successfully used for still image classification. The most commonly used are SIFT [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF], SURF [START_REF] Bay | Surf: Speeded up robust features[END_REF] and Histogram of oriented gradient (HOG) [START_REF] Dalal | Human detection using oriented histograms of flow and appearance[END_REF]. SIFT and SURF are both interest points detector and local image descriptor. In this paper, we only consider the descriptors. SIFT and HOG descriptors rely on a histogram of orientation of gradient. Locally, the orientation of the gradient is quantized in o orientations (typically 8). For a given spatial window, a HOG (or a SIFT) descriptor is computed by decomposing the window with a grid of N × N cells. Each cell contains the histogram of orientations of the gradient. The descriptor is obtained by the concatenation of the N × N histograms.

The SURF [START_REF] Bay | Surf: Speeded up robust features[END_REF] descriptor has been developed as a faster alternative to SIFT. In the case of SURF, descriptors of each cells are computed using weighted sum of responses to 2D Haarwavelets along horizontal axis (dx) and vertical axis (dy), the absolute value of dx and the absolute value of dy.

More recently, new descriptors have been proposed with the aim to decrease the computation time without loss of performance. The GLOH [START_REF] Mikolajczyk | A performance evaluation of local descriptors[END_REF] is an extension of the SIFT, in which the rectangular grid is replaced by a polar grid. The authors propose to use 3 bins in radial direction and 8 in angular direction. The gradient orientation is quantized in 16 bins inside each cell. To reduce the dimension of the descriptor, a principle components analysis (PCA), computed on several GLOH, is applied. Similarly, Daisy [START_REF] Tola | Daisy: An efficient dense descriptor applied to wide-baseline stereo[END_REF] is a SIFT like descriptor designed to be faster to compute in the case of dense matching extraction. The sum in histogram cells are replaced by computing the convolution of the orientation maps with Gaussian kernels. Moreover, the sampling positions of the descriptor are not aligned with a rectangular grid, but in concentric circles at several distances to the descriptor center. For a given distance, the sample points are associated to a particular Gaussian kernel size, increasing with the distance to the center.

Action descriptors

In the early work on action recognition, silhouette based descriptors, also called motion appearance models were used. These descriptors are computed from the evolution of a silhouette obtained by background subtraction methods or by taking the difference of frames (DOF). From a sequence of binary images, Bobick and Davis [START_REF] Davis | The representation and recognition of action using temporal templates[END_REF] propose descriptors called "Motion Energy Image" (MEI) representative of the energy of movement and "Motion History Image" (MHI) providing information about the chronology of motion. These two descriptors are modeled by seven Hu moments. In [START_REF] Kellokumpu | Texture Based Description of Movements for Activity Analysis[END_REF] Kellokumpu et al. use histograms of "Local Binary Patterns" (LBP) [START_REF] Ojala | Multiresolution gray-scale and rotation invariant texture classification with local binary patterns[END_REF] to model the MHI and MEI images. In [START_REF] Kellokumpu | Human activity recognition using a dynamic texture based method[END_REF], they propose an extension of the LBP directly applied on the image pixels with successful results. Wang and Suter [START_REF] Wang | Learning and matching of dynamic shape manifolds for human action recognition[END_REF] use two other descriptors, namely the "Average Motion Energy" (AME) and the "Mean Motion Shape" (MMS). The AME is a descriptor close to the MHI representing the average image of silhouettes. The MMS is defined from boundary points of the silhouette in complex coordinates with the origin placed at the centroid of the 2D shape. As time is an important information in video, Gorelick et al. [START_REF] Blank | Actions as space-time shapes[END_REF][START_REF] Gorelick | Actions as space-time shapes[END_REF] study the silhouettes as space-time volumes. Space-time volumes are modeled with Poisson equations. From these, they extract seven spatio-temporal characteristic components.

The main drawback of all these methods is the computation of silhouettes. Indeed, this computation is not very robust, making these methods only relevant in controlled environments such as the Weizmann dataset [START_REF] Blank | Actions as space-time shapes[END_REF] and the KTH dataset [START_REF] Schuldt | Recognizing human actions: A local svm approach[END_REF]. However, they tend to fail on more realistic data-sets such as UCF11 [START_REF] Liu | Recognizing realistic actions from videos in the wild[END_REF] or Hollywood2 [START_REF] Laptev | Learning realistic human actions from movies[END_REF] datasets.

Assuming that action recognition is closely linked to the notion of movement, many authors have proposed descriptors based on the modeling of optical flow. The optical flow represents the displacement of pixels from two consecutive frames. The result can be represented by vector field with two components. Here, U denotes the horizontal component of motion and V the vertical component. Early works with respect to this approach were proposed by Polana and Nelson [START_REF] Polana | Low level recognition of human motion[END_REF]. The vector field is first decomposed according to a spatial grid. Then, in each cell of the grid, the magnitude of motion is accumulated. This method can only process periodic actions such as running or walking.

Efros et al. [START_REF] Efros | Recognizing action at a distance[END_REF] propose a descriptor computed on a figurecentric spatio-temporal volume for each person in a video. The vector field representing the motion between two consecutive frames of the volume is computed with the Lucas and Kanade optical flow algorithm [START_REF] Lucas | An iterative image registration technique with an application to stereo vision[END_REF]. The two components U and V of the vector field are decomposed with a half-wave rectification technique. The resulting four components are blurred using a Gaussian filter and normalized. They are directly used as a descriptor. The obtained descriptors are compared using the normalized correlation measure. This descriptor is used and/or extended by several authors in [START_REF] Fathi | Action recognition by learning mid-level motion features[END_REF][START_REF] Danafar | Action recognition for surveillance applications using optic flow and svm[END_REF].

Tran et al. propose the motion context descriptor in [START_REF] Tran | Human activity recognition with metric learning[END_REF]. It is also a figure-centric descriptor based on the silhouette extraction. They use the vector field and the binary silhouette as three components. The components of the field are blurred with a median filter. Then, the three components are subdivided with a grid of 2 × 2 cells. Each cell is decomposed in 18 radial bins, each covering 20 degrees. Inside the radial bins, the sum of each component is computed. This provides, for each component, 4 histograms composed with 18 bins. The concatenation of these histograms provides a 216-dimensional vector which is the movement pattern of a given field. From this pattern, the "Motion Context" is created. It is composed of the 216dimensional vector of the current frame plus the first 10 vectors of the PCA models of the 5 previous frames, the first 50 vectors of the PCA models of 5 current frames and finally the first 10 vectors PCA models of 5 next frames.

Ali and Shah [START_REF] Ali | Human action recognition in videos using kinematic features and multiple instance learning[END_REF] begin by computing many kinematic features on the field and then compute kinematic modes with a spatio-temporal principal component analysis.

Finally, the most successful descriptors developed in recent years are extensions to video of still image descriptors. The most commonly used are the Histogram of Oriented Flow (HOF) [START_REF] Dalal | Human detection using oriented histograms of flow and appearance[END_REF] and the Motion Boundary Histogram (MBH) [START_REF] Dalal | Human detection using oriented histograms of flow and appearance[END_REF]. HOF is the same as HOG but is applied to optical flow instead of gradient. The MBH models the spatial derivatives of each component of the optical flow vector field with a HOG.

In this context, several extension of still image descriptors have been proposed. The cuboid [START_REF] Dollár | Behavior recognition via Table 10: Mean Average Precision on the UCF11 dataset ; ND: number of descriptors ; NL: non-linear classifiers[END_REF] is a space-time descriptor, represented by a space-time volume. For a given volume, the gradient is computed on the three directions and the descriptor are the flattening of the gradient in a vector. Consistent with this, Klaser et al. [START_REF] Klaser | A spatio-temporal descriptor based on 3d-gradients[END_REF] extend HOG to 3DHOG. A 3dimensional extention of SIFT is proposed in [START_REF] Scovanner | A 3-dimensional sift descriptor and its application to action recognition[END_REF]. ESURF [START_REF] Willems | An efficient dense and scaleinvariant spatio-temporal interest point detector[END_REF] is an extention of SURF with 3D Haar-wavelets.

Descriptors based on a polynomial approach for modeling global optical flow are proposed in [START_REF] Kihl | Human activities discrimination with motion approximation in polynomial bases[END_REF] and [START_REF] Mota | A tensor based on optical flow for global description of motion in videos[END_REF]. From this preliminary works, a local descriptor for motion named Series of Polynomial approximation of Flow (SoPAF) is proposed in [START_REF] Kihl | Local polynomial space-time descriptors for actions classification[END_REF]. The descriptor is based on two local modeling, a spatial model and a temporal model. The spatial model is computed by the projection of the optical flow onto bivariate orthogonal polynomials. Then, the time evolution of spatial coefficients is modelled with a one dimension polynomial basis.

Recently, Wang et al. [START_REF] Wang | Action recognition by dense trajectories[END_REF] propose to model these usual descriptors along dense trajectories. The time evolution of trajectories, HOG, HOF and MBH is modelled using a space time grid following pixels trajectories. The use of dense trajectories for descriptor extraction tends to increase the performances of popular descriptors (HOG, HOF and MBH).

Signatures

Once a set of descriptors is obtained from the video, a popular way of comparing images (or videos) is to map the set of descriptors into a single vector and then to measure the similarity between the obtained vectors (for example in [START_REF] Sánchez | Modeling the spatial layout of images beyond spatial pyramids[END_REF], [START_REF] Wang | Evaluation of local spatio-temporal features for action recognition[END_REF] and [START_REF] Wang | Action recognition by dense trajectories[END_REF]). The most common method for such embeddings is inspired by the text retrieval community and is called the "Bag of Words" (BoW) approach [START_REF] Sivic | Video google: A text retrieval approach to object matching in videos[END_REF]. It consists in computing a dictionary of descriptor prototypes (usually by clustering a large number of descriptors) and then computing the histogram of occurrences of these prototypes (called "Visual Words") within the set.

In still images classification, these approaches have been formalized in [START_REF] Wang | Locality-constrained linear coding for image classification[END_REF] by a decomposition of the mapping into two steps. The first step, namely the "coding step", consists in mapping each descriptor into a codeword using the aforementioned dictionary. The second step is to aggregate the codewords into a single vector and is called the "pooling step". Structural constraints such as sparsity [START_REF] Yang | Linear spatial pyramid matching using sparse coding for image classification[END_REF] or locality [START_REF] Wang | Locality-constrained linear coding for image classification[END_REF] can be added to the coding process to ensure most of the information is retained during the pooling step. Common pooling processes include averaging the codewords or retaining the entry-wise maximum among the codewords (max pooling). Extensions of the BoW model have been recently proposed to include more precise statistical information. In [START_REF] Avila | Bossa: Extended bow formalism for image classification[END_REF], the authors propose to model the distribution of distances of descriptors to the clusters centers. In the "coding/pooling" framework, each descriptor is coded by 1 in the bin corresponding to its distance to the cluster's center to which it belongs, and 0 otherwise. The polling is simply the averaging over all codewords.

In [START_REF] Jégou | Aggregating local descriptors into a compact image representation[END_REF], the authors proposed a coding process where the deviation between the mean of the descriptors of the set and the center of the cluster to which they belong to is computed. The whole mapping process can be seen as the deviation between a universal model i.e. the dictionary) and a local realization (i.e. the set of descriptors). Using this model deviation approach, higher order statistics have been proposed, like "super-vectors" in [START_REF] Zhou | Image classification using supervector coding of local image descriptors[END_REF], "Fisher Vectors" in [START_REF] Jégou | Aggregating local image descriptors into compact codes[END_REF] or "VLAT" in [START_REF] Picard | Efficient image signatures and similarities using tensor products of local descriptors[END_REF][START_REF] Picard | Improving image similarity with vectors of locally aggregated tensors[END_REF]. Fisher Vectors are known to achieve state of the art performances in image classification challenges [START_REF] Chatfield | The devil is in the details: an evaluation of recent feature encoding methods[END_REF].

To compare the performances of descriptors, in this paper, we consider a compressed version of VLAT which is known to achieve near state of the art performances in still images classification with very large sets of descriptors [START_REF] Negrel | Using spatial pyramids with compacted vlat for image categorization[END_REF]. In our case, the dense sampling both in spatial and temporal directions leads to highly populated sets, which is consistent with the statistics computed in VLAT signatures. Given a clustering of the descriptors space with C clusters computed on some training set, the first and second order moments µ c and τ c are computed for each cluster c:

µ c = 1 |c| i r ν rci (1)
τ c = 1 |c| i r (ν rci -µ c )(ν rci -µ c ) T (2)
with ν rci the descriptor r of the video i which is in cluster c, and |c| being the number of descriptors ν rci of video i in cluster c, for all videos in the training set. To allow a dimension reduction of the signature, the eigen decomposition of the covariance matrix τ c for each cluster c is then performed:

τ c = V c D c V c (3)
Using this decomposition, descriptors are projected on the subspace generated by the eigenvectors V c . The compressed VLAT signature τ i,c of video i is computed for each cluster c with the following equation:

τ i,c = r (V c (ν rci -µ c ))(V c (ν rci -µ c )) -D c (4)
τ i,c are then flattened into vectors v i,c . The complete VLAT signature x i of video i is obtained by concatenation of v i,c for all clusters c:

v i = (v i,1 . . . v i,C ) (5)
It is advisable to perform a normalization step for best performance.

∀ j, v i [ j] = sign(v i [ j])|v i [ j]| α , (6)
x i = v i v i (7)
With α = 0.5 typically. The size of the compacted VLAT signature depends on the number d c of eigenvectors retained in each cluster, and is equal to

c d c (d c +1) 2
(thanks to the matrices τ i,c being symmetric, only half of the coefficients are kept).

Primitive/Coding/Aggregation framework

In this section, we present the main contribution of this paper. We propose a framework providing a formal description of the steps needed to design local visual descriptors. Our framework splits descriptors extraction in three levels: primitive extraction, primitive coding and code aggregation.

Primitive extraction

At the primitive level, we extract a specific type of low-level information from an image or a video. Such primitives include the gradient (HOG), the responses to 2D Haar-wavelets (SURF), the motion flow (HOF), or the gradient of motion flow (MBH). In Fig. 1, we show three examples of primitive used in literature, the gradient, the motion flow and the gradient of the motion flow. The objective is to extract local properties of the signal. Generally, it relies on a high frequency filtering, linear for gradient or non-linear in the case of motion (optical flow), filters banks such as Haar (SURF), easy extension of popular filters [START_REF] Varma | A statistical approach to material classification using image patch exemplars[END_REF], or non-linear operators. The primitive extraction induces a choice in relevant information and introduces data loss.

Primitive coding

The primitive coding corresponds to a non-linear mapping of the primitive to a higher dimensional space. The objective is to improve the representation by grouping together the primitive properties that are similar.

In the literature, the most popular primitive coding is the quantization of local vector field orientations [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF][START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF]. The quantization is usually performed on 8 bins. Let G x (x),G y (x) be the horizontal and vertical derivative of an image at position x, the principal orientation bin is computed by:

o(x) = (atan2(G y (x), G x (x)) mod 2π) × 4 π (8)
In order to limit the effect of floor on coding, the distance to the next orientation bin is computed by

r(x) = o(x) - (atan2(G y (x), G x (x)) mod 2π) × 4 π (9)
The value associated to the bin o(x) and o(x) + 1 are

O(x, o(x)) = ρ(x) × (1 -r(x)) (10) O(x, (o(x) + 1) mod 8) = ρ(x) × r(x) (11)
with ρ(x) the magnitude of horizontal and vertical derivative (ρ(x) = G x (x) 2 + G y (x) 2 ). This primitive coding do not introduce any loss of information or redundancy. Another primitive coding is proposed in SURF [START_REF] Bay | Surf: Speeded up robust features[END_REF]. Here, we call it "absolute coding". In the SURF descriptor, it is applied to the gradient primitive. This is a four dimension code defined as:

A(x, 0) = G x (x) (12) A(x, 1) = G y (x) (13) A(x, 2) = |G x (x)| (14) A(x, 3) = |G y (x)| (15)
This primitive coding introduces redundancy. However, it produces lower dimensions code than orientation coding.

In the context of action recognition and classification, the rectified coding proposed by Efros et al. . [START_REF] Efros | Recognizing action at a distance[END_REF] has been used by several authors. They decompose the horizontal (U) and vertical (V) components of a vector field (usually obtained by optical flow approaches) with a technique of half-wave rectification:

R(x, 0) = U(x) if U(x) > 0 0 else (16) R(x, 1) = |U(x)| if U(x) < 0 0 else (17) R(x, 2) = V(x) if V(x) > 0 0 else (18) R(x, 3) = |V(x)| if V(x) < 0 0 else (19)
Orientation coding, absolute coding and rectified coding are the most used in literature.

We also propose a new primitive coding called double rectified coding. This coding corresponds to the 4 components of the rectified coding and the 4 components of the absolute coding. Examples of these primitive coding are shown in Fig. 2.

Code Aggregation

Finally, the code aggregation is used to model the encoded primitives. The objective of aggregation is to improve the robustness to deformation by allowing inexact matching between deformed image or video patches. Most descriptors from the literature (HOG, HOF, MBH, SURF) use accumulation of each primitive coding (typically with a simple sum). In order to improve robustness, the accumulation is done on the cell of a grid of N × N cells. In the case of video, the grid could be extended in N × N × T cells with T the number of cell bins in time direction. The spatial window could be pondered by a Gaussian to give more importance to the cells which are close to the center, like in SIFT. We show a 4 × 4 cell aggregation in Fig. 3a.

The regular grid can replaced with concentric circles arranged in a polar manner, as it is proposed in DAISY [START_REF] Tola | Daisy: An efficient dense descriptor applied to wide-baseline stereo[END_REF]. The final pattern resembles a flower, and is shown in Fig. 3b. In the following, we name this code aggregation "Flower". The flower aggregation is defined by three parameters R, Q and T . The radius R defines the distance from the center pixel to the outer most grid point. The quantization of the radius Q defines the number of convolved primitives layer associated to different size of Gaussian (Q = 3 in Fig. 3b). The parameter T defines the angular quantization of the pattern at each layer (T = 8 in Fig. 3b).

The aggregation proposed in [START_REF] Kihl | Human activities discrimination with motion approximation in polynomial bases[END_REF] is based on the projection of primitive on a two dimensional orthogonal polynomial basis. The family of polynomial functions with two real variables is defined as follows:

P K,L (x 1 , x 2 ) = K k=0 L l=0 a k,l x k 1 x l 2 (20)
B = {B 0,0 , B 0,1 , • • • , B 0,L , B 1,0 , • • • • • • , B 1,L-1 , • • • , B K-1,0 , B K-1,1 , B K,0 } (21)
An orthogonal basis can be created using the following three terms recurrence:

                   B -1,l (x)=0 B k,-1 (x)=0 B 0,0 (x)=1 B k+1,l (x)=(x 1 -λ k+1,l )B k,l (x)-µ k+1,1 B k-1,l (x) B k,l+1 (x)=(x 2 -λ k,l+1 )B k,l (x)-µ k,l+1 B k,l-1 (x) (22)
where x = (x 1 , x 2 ) and the coefficients λ k,l and µ k,l are given by

λ k+1,l = x 1 B k,l (x)|B k,l (x) B k,l (x) 2 λ k,l+1 = x 2 B k,l (x)|B k,l (x) B k,l (x) 2 µ k+1,l = B k,l (x)|B k,l (x) B k-1,l (x) 2 µ k,l+1 = B k,l (x)|B k,l (x) B k,l-1 (x) 2 (23)
and • | • is the usual inner product for polynomial functions:

B 1 | B 2 = Ω B 1 (x)B 2 (x)w(x)dx (24)
with w the weighting function that determines the polynomial family and Ω the spatial domain covered by the window W(i, j, t). Legendre polynomials (w(x) = 1, ∀x) are usually used.

Using this basis, the approximation of a decomposed primitive component P is:

P = D k=0 D-k l=0 ũk,l B k,l (x) B k,l (x) (25)
The polynomial coefficients ũk,l are given by the projection of component U onto normalized B elements:

pk,l = P | B k,l (x) B k,l (x) (26)
We show the polynomials associated to a 4 degree basis in Fig. 3c. The polynomials are defined in a spatial domain of 32 × 32 pixels. In the case of video classification, space-time aggregation is considered. Kihl et al. . propose [START_REF] Kihl | Human activities discrimination with motion approximation in polynomial bases[END_REF] to model spatial polynomial coefficients with a d degree temporal basis of Legendre polynomial defined by

                       B -1 (t) = 0 B 0 (t) = 1 T n (t) = (t -tB n-1 (t)|B n-1 (t) )B n-1 (t) -B n-2 (t) B n (t) = T n (t) |T n | (27)
Using this basis of degree d, the approximation of P k,l (i, j, t) is:

pk,l (i, j, t) = d n=0 pk,l,n (i, j, t) B n (t) B n (t) (28)
The model has d + 1 coefficients pk,l (i, j, t) given by pk,l,n (i,

j, t) = p k,l (i, j, t) | B n (t) B n (t) (29)
The time evolution of a given coefficient pk,l (i, j) is given by the vector m l,k (i, j, t 0 ) as defined in equation [START_REF] Willems | An efficient dense and scaleinvariant spatio-temporal interest point detector[END_REF] m l,k (i, j, t 0 ) = [ pk,l,0 (i, j, t 0 ), pk,l,1 (i, j, t 0 ), . . . , pk,l,d (i, j, t 0 )]

Finally, the descriptor is the concatenation of all the m l,k (i, j, t 0 ) vectors for each coded primitive. In this paper, we also propose an easy extension of this aggregation using a Sine basis, in place of the Legendre polynomials.

A unified framework for descriptors

In Table 1, we summarize the different primitives, coding and aggregations currently used for classification. According to specific combinations of primitive, coding and aggregation, we can explain most of the usual descriptors. In Table 2 used to produce efficient descriptors. Indeed, our framework allows to explore and evaluate the possible combinations so as to find the best descriptors.

Experiments

In the experiments, we compare several combination of primitives, coding and aggregations provided by our framework in order to evaluate still image descriptors and action descriptors. As dense sampling outperforms key-point extraction [START_REF] Everingham | The PASCAL Visual Object Classes Challenge[END_REF][START_REF] Wang | Action recognition by dense trajectories[END_REF] for categories recognition, we use dense sampling in all our experiments. We carry out experiments on an image dataset (VOC2007) and three well known human action recognition datasets (KTH dataset [START_REF] Schuldt | Recognizing human actions: A local svm approach[END_REF], Hollywood2 Human Actions dataset [START_REF] Laptev | Learning realistic human actions from movies[END_REF] and UCF11 [START_REF] Liu | Recognizing realistic actions from videos in the wild[END_REF]).

For the experiments, we obtain signatures from our descriptors by using the VLAT indexing method [START_REF] Negrel | Compact tensor based image representation for similarity search[END_REF] as explained in section 2.3.

Still image classification

We first present results on still image categorization. The gradient is the only primitive considered. The gradient is extracted with the simple one order approximation difference method, at a single resolution.

Pascal VOC 2007 dataset

The PASCAL-VOC 2007 dataset [START_REF] Everingham | The PASCAL Visual Object Classes Challenge[END_REF] consists in about 10,000 images and 20 categories, and is divided into 3 parts: "train", "val" and "test". We use linear SVM classifier trained on "train" + "val" sets and tested on the "test" set.

We use four primitive coding: absolute, rectified, double rectified and orientation. These coding are combinatorially associated to the following three code aggregations: regular cells, flower and polynomials basis. For the regular grid aggregation, we use 4 × 4 cells. The cells are evaluated at four scales: 4 × 4 pixels, 6 × 6 pixels, 8 × 8 pixels and 10 × 10 pixels. For the flower aggregation, the parameter Q is set to 3 and the parameter T is set to 8. We consider the flower aggregation at four scales by setting radius R at 9 pixels, 12 pixels, 15 pixels and 18 pixels. For the polynomial aggregation, we set the basis degree to 4. The polynomial spatial domain is considered at four scales: 16 × 16 pixels, 24 × 24 pixels, 32 × 32 pixels and 40 × 40 pixels.

For the VLAT signature, the number of projectors in equation ( 3) is set to 70. We use a dictionary of 256 visual words. 3. We remark orientation coding clearly outperforms the other primitive coding for all the code aggregations experimented on this dataset. The GoF, GoC and GoP (c.f. Table 3) provide the best results. We remark that the three features with highest mean average precision are GoC, GoF and GoP for each category of the VOC2007 dataset. Using a simple concatenation of the signatures, we obtain 64.2% of mean average precision.

This result is reported in table 4 and compared with the results from [START_REF] Sánchez | Modeling the spatial layout of images beyond spatial pyramids[END_REF]. Note that our approach provides a global image signature which does not include any kind of spatial information like Spatial Pyramidal Matching (SPM) [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF] or object detectors [START_REF] Li | Object bank: A high-level image representation for scene classification and semantic feature sparsification[END_REF]. We compare our results to those of Sanchez et al. [START_REF] Sánchez | Modeling the spatial layout of images beyond spatial pyramids[END_REF] which gives results without spatial information. In [START_REF] Sánchez | Modeling the spatial layout of images beyond spatial pyramids[END_REF] the SIFT descriptors are highly dense extracted at 7 resolutions and then aggregated with the Fisher Vector signature approach. We show that our framework allows easy extension of HOG (GoC), for example by changing the codes aggregation from cell to polynomial. According to this new descriptor, we improve the categorization results obtained with only HOG descriptors. Moreover, our framework is compatible with adding spatial information like in [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF], which should further improve the results.

Video actions recognition

In this section, we present results on video actions recognition. First, we evaluate our framework on the KTH [START_REF] Schuldt | Recognizing human actions: A local svm approach[END_REF] dataset. Then, we evaluate our method on two more challenging datasets of the literature, Hollywood2 [START_REF] Laptev | Learning realistic human actions from movies[END_REF]) and UCF11 [START_REF] Liu | Recognizing realistic actions from videos in the wild[END_REF] and compare our results to that of the literature. We compare three primitive extractions (gradient, motion and gradient of motion), three primitive coding (raw, rectified and orientations) and three code aggregations (cells, polynomials and sinus). We extract the gradient with the simple one order approximation difference method. For motion estimation, we use a Horn and Schunk optical flow algorithm [START_REF] Horn | Determining optical flow[END_REF] with 25 iteration and the regularization λ parameter is set to 0.1. We extract the primitives at 1 resolution for KTH, 7 resolutions for Hollywood2 and 5 resolutions for UCF11. The resolution factor is set to 0.8 . The resolutions are obtained by down sampling images, we do not use any up sampling in this work. We aggregate the extracted descriptors with the compressed VLAT signature approach as defined in the section 2.3.

Evaluation of our framework on KTH dataset

The KTH dataset [START_REF] Schuldt | Recognizing human actions: A local svm approach[END_REF] contains six types of human actions: walking, jogging, running, boxing, hand waving and hand clapping (Fig. 5). These actions are performed by 25 different subjects in four scenarios: outdoors, outdoors with scale variation, outdoors with different clothes, inside. For all experiments, we use the same experimental setup as in [START_REF] Schuldt | Recognizing human actions: A local svm approach[END_REF][START_REF] Wang | Action recognition by dense trajectories[END_REF], where the videos are divided into a training set (8 persons), a validation set (8 persons) and a test set (9 persons). The best hyperparameters are selected through cross-validation using the training and validation sets. The classification accuracy results are obtained on the test set.

We experiment several descriptors according to our framework for several spatial and time modeling. We present on Tables 5, 6 and 7 the main results obtained for each primitive extraction on KTH dataset. We present in Table 5 the results associated with the gradient primitive. As for still image experiments, the orientation coding clearly outperforms the other primitive coding for the three code aggregations. When the orientation coding is associated with the cell aggregation, it produces the best results for the gradient primitive extraction. The best results are obtained for code aggregations with the lower level of modeling along time axis for all code aggregations. We present in Table 6 the results associated with the motion primitive. In the case of motion primitive, the rectified coding allows to obtain good results for polynomial aggregation and sine aggregation. For the motion primitive, higher time modeling improves the results for a given spatial modeling. For instance, for the rectified coding and the polynomial aggregation with a spatial polynomial basis of degree 2, if the time polynomial basis is of degree 2 the classification accuracy is 90.5% and if the time polynomial basis is of degree 4, the accuracy is 91.7.

We present in Table 7 the results associated with the gradient of motion primitive. The best results, for each code aggregation, are obtained with rectified coding. It is interesting to note that we have only generated descriptors whose size does not exceed 144 dimensions. Note the motion of gradient primitive provides 4 components and the orientation coding decomposes each components in 8 orientation maps. So, the size of descriptors associating Motion of gradient primitive and orientation coding are easily of high dimension.

We present in Table 8 the classification accuracy results of several combinations of descriptors on KTH. We show the best descriptor results of our study for each primitives and codes aggregation, and compare them to recent results from the literature. Every single descriptor presented in Table 8 are comparable to those proposed by Wang et al. in [START_REF] Wang | Action recognition by dense trajectories[END_REF]. Moreover, simple concatenation of all our signature (9) outperform the classification accuracy of Wang [START_REF] Wang | Action recognition by dense trajectories[END_REF] and Gilbert [START_REF] Gilbert | Action recognition using mined hierarchical compound features[END_REF]. Let us note that our approach uses linear classifiers, and thus leads to better efficiency both for training classifiers and classifying video shots, as opposed to methods of [START_REF] Wang | Action recognition by dense trajectories[END_REF] and [START_REF] Gilbert | Action recognition using mined hierarchical compound features[END_REF]. Moreover, we do not used dense trajectory to follow descriptors along time axis as in [START_REF] Wang | Action recognition by dense trajectories[END_REF].

Comparison to State of the art

For further experiments and comparisons to literature on Hollywood2 and UCF11 dataset, we use the nine best descriptors identified thanks to our experiments on KTH dataset.

Hollywood dataset

The Hollywood2 [START_REF] Laptev | Learning realistic human actions from movies[END_REF] dataset consists of a collection of video clips and extracts from 69 films in 12 classes of human actions (Fig. 6). It accounts for approximately 20 hours of video and contains about 150 video samples per actions. It contains a variety of spatial scales, zoom camera, deleted scenes and compression artifact which allows a more realistic assessment of human actions classification methods. We use the official train and test splits for the evaluation.

UCF11 dataset

The UCF11 [START_REF] Liu | Recognizing realistic actions from videos in the wild[END_REF] dataset is an action recognition data set with 11 action categories, consisting of realistic videos taken from youtube (Fig. 7). The data set is very challenging due to large variations in camera motion, object appearance and pose, object scale, viewpoint, cluttered background and illumination conditions. The videos are grouped into 25 groups, where each group consists of more than 4 action clips. The video clips in the same group may share some common features, such as Method ND NL Results Wang (HOG+traj) [START_REF] Wang | Action recognition by dense trajectories[END_REF] 1 X 86.5% Wang (HOF+traj) [START_REF] Wang | Action recognition by dense trajectories[END_REF] 1 X 93.2% Wang (MBH+traj) [START_REF] Wang | Action recognition by dense trajectories[END_REF] 1 X 95.0% Wang (All) [START_REF] Wang | Action recognition by dense trajectories[END_REF] 4 X 94.2% Gilbert [START_REF] Gilbert | Action recognition using mined hierarchical compound features[END_REF] 3

X 94.5% A = Gradient + ori + Cell (4,

Results

We select the best setup according to gradient primitive associated with cells and polynomials projections (c.f. Table 5), the best setup according to Motion primitive associated with cells and polynomials projections (c.f. Table 6) and the best setup according to Gradient of motion primitive associated with cells and polynomials projections (c.f. Table 7). These setups are evaluated on the Hollywood2 dataset and results are reported in Table 9. The results presented here improve the state of the art for single descriptor setups when comparing to HOG (gradient primitive), to HOF (motion primitive) and to MBH (gradient of motion primitive). Note that, opposed to [START_REF] Wang | Action recognition by dense trajectories[END_REF], we do not use the dense trajectories to obtain these results. Our framework allows to increase the number of descriptor for a fixed number of primitives. Finally, by combining nine primitives, we obtain a mean average precision of 60.2%.

We evaluate the same descriptors on the UCF11 dataset and we report our results in Table 10. On UCF11 dataset, for all the primitives extraction, the cell aggregation and polynomial aggregation improve the results of Wang et al. [START_REF] Wang | Action recognition by dense trajectories[END_REF] for single descriptor corresponding to that primitive. However, the Sine aggregation produces lower results in the case of Gradient primitive and Gradient of Motion primitive. When combining descriptors, we improve the results of Wang et al. [START_REF] Wang | Action recognition by dense trajectories[END_REF] without using dense trajectories. The results obtained on the challenging UCF11 and Hollywood2 datasets with the combination of several descriptors highlight the soundness of our framework. Using our framework, we experimented several combination of primitives extraction, primitive coding and code aggregation, some of them being drawn from the most popular descriptors. We obtain better or equivalent results for than the usual descriptors of literature on a popular still image categorization dataset and on three well known videos recognition datasets. This confirms the validity and relevance of our framework to create new descriptors. We are confident our framework can be used to implement descriptors families not covered in this paper (for example dense trajectories).

Furthermore, it is interesting to compare our framework to the coding/pooling approaches [START_REF] Wang | Locality-constrained linear coding for image classification[END_REF] tors using our framework. For example, dictionary based approaches [START_REF] Sivic | Video google: A text retrieval approach to object matching in videos[END_REF][START_REF] Wang | Locality-constrained linear coding for image classification[END_REF] and model deviation approaches [START_REF] Jégou | Aggregating local descriptors into a compact image representation[END_REF][START_REF] Jégou | Aggregating local image descriptors into compact codes[END_REF][START_REF] Picard | Improving image similarity with vectors of locally aggregated tensors[END_REF] can be used for the coding and aggregation steps. Future work also involves the optimization of the primitive step by using machine learning algorithms. For example, the primitive can be an adapted filter bank trained on some training set, in a similar way of the deep learning approaches [START_REF] Farabet | Learning hierarchical features for scene labeling[END_REF] or the infinite kernel learning approaches [START_REF] Rakotomamonjy | Learning with infinitely many features[END_REF].

Figure 1 :

 1 Figure 1: Example of primitive ; (a) Horizontal gradient ; (b) Vertical gradient ; (c) horizontal motion flow ; (d) Vertical motion flow ; (e) Horizontal gradient of horizontal motion flow ; (f) Vertical gradient of horizontal motion flow ; (g) Horizontal gradient of vertical motion flow ; (h) Vertical gradient of vertical motion flow

Figure 2 :

 2 Figure 2: Example of coding ; on the first line: Absolute coding of the gradient primitive (A(0), A(1), A(2), A(3) ; on the second line: Rectified coding of the gradient primitive (R(0), R(1), R(2), R(3)) ; on the third and fourth lines: Orientation coding of the gradient primitive (O(0), O(1), O(2), O(3), O(4), O(5), O(6), O(7)) ;

Figure 3 :

 3 Figure 3: Examples of aggregation ; (a) 4 × 4 cells aggregation ; (b) Flower aggregation with Q = 3 and T = 8; (c) Representaion of 4 degree basis spatial polynomials aggregation

Figure 4 :

 4 Figure 4: Images from PASCAL Visual Object Classes Challenge 2007

Figure 5 :

 5 Figure 5: Example of videos from KTH

Figure 6 :

 6 FightPersonHugPerson

Figure 7 :

 7 Figure 7: Example of videos from UCF11

Table 1 :

 1 A new framework for local descriptors

Table 2 :

 2 , we explain the usual descriptors of the literature with our framework. Each new Primitive, Coding or Aggregation defines a new family of descriptors and each new combination of Primitive-Coding-Aggregation defines a new descriptor. Since different primitives correspond to different properties of the signal, we argue that adapted coding and aggregation schemes have to be Rewriting of the usual descriptors ; raw means the vector field is represented by the horizontal and vertical components

	Name	Primitive	Coding	Aggregation
	HOG	gradient	orientations	Regular cells
	Daisy	gradient	orientations	Flower
	HOF	motion	orientations	Regular cells
	MBH motion gradient orientations	Regular cells
	SURF	Haar	abs	cells
	Efros	motion	rectified	Regular cells
	SoPAF	motion	raw	polynomial basis

Table 4 :

 4 Image classification results on Pascal VOC 2007 dataset

				mAP aeroplane bicycle	bird	boat bottle	bus
			Our method	64.2	83.3	73.0	59.9	73.5	33.2	71.2
			SIFT + FV [34]	62.7	80.2	69.1	52.8	72.9	37.6	69.5
				car	cat	chair	cow	table	dog	horse
			Our method	84.2	65.7	53.3	49.5	58.8	52.3	83.0
			SIFT + FV [34]	81.8	61.8	54.9	47.2	61.5	50.5	79.1
				bike	person	plant	sheep sofa	train	tv
			Our method	72.0	87.5	37.2	47.4	55.4	85.5	58.0
			SIFT + FV [34]	67.1	85.8	37.6	46.6	57.0	82.3	59.0
	name	Coding	Aggregation	mAP usual name
	GaC	absolute	regular cells	58,2	SURF
	GaF	absolute	flower	56,6	x
	GaP	absolute	polynomial basis 57.6	x
	GrC	rectified	regular cells	58.1	x
	GrF	rectified	flower	57.2	x
	GrP	rectified	polynomial basis 57.4	x
	GoC	orientation	regular cells	63.2	HOG
	GoF	orientation	flower	63.7	DAISY
	GoP	orientation polynomial basis 63.2	x
	GdC	double	regular cells	58,2	x
	GdF	double	flower	56,9	x
	GdP	double	polynomial basis 57,8	x

Table 3 :

 3

Classification results exprimed by mean average precision for combination of primitives, coding and aggregations on VOC2007 dataset

Table 5 :

 5 Results for combination of gradient primitives, coding and aggregation on the KTH dataset ; dim means the dimension of the descriptor ; coding represent the code primitives (raw, rectified or orientation) ; SP means the number of spatial cells or the degree D of spatial polynomials or the spatial degree of the sinus basis ; TP means the number of temporal cells, or the degree d of temporal polynomials or the degree of sinus basis

									dim coding	Flow Cell Poly Sinus	SP TP	Usual name
									32	raw	87.0			4	1	x
									32	raw			85.1	3	0	x
									36	raw		89.8		2	2	SoPAF
									40	raw	89.6			2	5	x
									40	raw			88.0	1	4	x
									64	raw		90.4		2	4	SoPAF
									80	raw		91.1		3	3	SoPAF
									48	rect	90.7			2	3	x
									48	rect			91.3	1	2	x
	dim coding 32 raw 36 raw 40 raw 40 raw 64 raw 80 raw	Gradient Cell Poly Sinus 80.4 81.0 82.8 86.8 84.5 83.1	SP TP 4 1 2 2 2 5 1 4 2 4 3 3	Usual name x x x x x x	60 64 64 72 80 80 128 144	rect rect rect rect rect rect rect rect	90.4 91.4 92.0	90.7 90.5 91.7	87.7 91.0	4 4 3 2 2 1 2 3	0 1 0 2 5 4 4 4	x x x x x x x x
	48 48 60 64 64	rect rect rect rect rect	84.8 86.5	83.2	88.5 83.3	1 2 4 4 3	2 3 0 1 0	x x x x x	96 96 120 128 128	ori ori ori ori ori	89.2 91.8	90.6	90.0 87.8	2 1 4 4 3	3 2 0 1 0	HOF x x HOF x
	72	rect		84.5		2	2	x
	80	rect	87.2			2	5	x
	80	rect			88.5	1	4	x
	128	rect		88.0		2	4	x
	144	rect	88.5			3	4	x
	96	ori	92.4			2	3	HOG
	96	ori			91.4	1	2	x
	120	ori		92.6		4	0	x
	128	ori	93.4			4	1	HOG
	128	ori			93.3	3	0	x

Table 6 :

 6 Results for combination of motion primitive, coding and aggregations on the KTH dataset ; The legend is the same as Table5

	dim coding	Gradient of Motion SP TP Cell Poly Sinus	Usual name
	48	raw	90.0	2	3	x
	48	raw	90.0	1	2	x
	60	raw	90.3	4	0	x
	64	raw	90.0	4	1	x
	72	raw	90.6	2	2	x
	80	raw	89.9	2	5	x
	80	raw	89.4	1	4	x
	128	raw	91.0	2	4	x
	32	rect	92.2	2	1	x
	32	rect	91.5	1	0	x
	48	rect	93.1	2	0	x
	96	rect	94.2	2	3	x
	96	rect	93.4	1	2	x
	120	rect	93.7	4	0	x
	64	ori	92.5	2	1	MBH
	64	ori	91.5	1	0	x
	96	ori	93.6	2	0	x

Table 7 :

 7 Results for combination of gradient of motion primitive, coding and aggregations on the KTH dataset ; The legend is the same as Table5

Table 8 :

 8 Classification accuracy on the KTH dataset ; ND means the number of descriptors used ; NL stands for non-linear classifiers ; In[START_REF] Gilbert | Action recognition using mined hierarchical compound features[END_REF], the same feature is iteratively combined with itself 3 times the same person, similar background or similar viewpoint. The experimental setup is a leave one group out cross validation.

Preprint submitted to Pattern Recognition December 1, 2014

Method ND NL Results

Gilbert [START_REF] Gilbert | Action recognition using mined hierarchical compound features[END_REF] 3 X 50.9% Ullah [52] HOG+HOF 2 X 51.8% Ullah [52] 2 X 55.3% Wang [START_REF] Wang | Action recognition by dense trajectories[END_REF]


A Dufour

J François

R Olcese

THE DIFFERENT SCALES OF THE THERMOCHEMICAL PROCESSING OF LIGNO-CELLULOSIC BIOMASS: CASE STUDIES

Keywords: green process, ligno-cellulosic biomass, gasification, pyrolysis, HDO

A general overview of the different routes for a thermochemical valorisation of lignicellulosic biomass is presented. The different scales involved range from the molecular level to the particle level, then to the reactor level, to the plant level and to the forest management. The work done at these levels will be illustrated by examples from two routes: the production of electrical energy and heat by gasification, and the production of BTX by pyrolysis of lignin from biorefinery followed by Hydrodeoxygenation.

Even if the prices of fossil fuels are currently on the decrease, it is highly probable that the oil peak is behind us. The coal and shale oil and gas reserves are still huge, but all these energy and base chemical sources produce large amounts of CO2 and the global warming will have dramatic consequences for the future generations. Replacing fossil fuels as far as possible by renewable ones is a duty for our generation. A part of the mix that should ensure a sustainable development is the use of biomass, either to produce electrical energy, or to produce valuable products.

Fig. 1 presents a global view of the chemical and energetic processes that can be used to upgrade different kinds of biomass, as seen by Gillenwater (Lanza Tech) [START_REF] Gillenwater | Fuel and Chemical Products from Biomass Syngas[END_REF] . Among the routes presented, only the upgrading of ligno-cellulosic biomass will be considered here, the ligno-cellulosic biomass being either wood residues or "energy" plants like miscanthus.

CASES CONSIDERED

Two cases will be discussed here: -The use of wood residues to produce syngas, that will be used to produce power and heat.

-The production of valuable chemicals by hydrotreatment of lignin obtained from wood.

Biomass gasification CHP process

Fig. 2 presents a schematic description of the whole route of such as it is investigated in our team. Evaluating such route and designing the different parts of equipment requires a interdisciplinary approach combining investigations at a number of scales:

-Production of the biomass: biomass that is in competition with food uses has to be avoided (the first generation biofuels are deadend), which leaves either plants dedicated to energy uses (trilicate, miscanthus, etc.) or wood, that of course has also other uses (furniture, construction, chemicals). The management of forests has been the subject of a considerable amount of research, also interdisciplinary (climate, sun irradiation, plant biology, etc.), that would be a subject by itself. This has been treated by our colleagues from forest science [START_REF] Dufour-Kowalski | [END_REF][3][4] : a Java-programme platform called CAPSIS hosts a number of forest growth models. It also includes a number of diagnostic tools (among which a Carbon Assessment tool) allowing to evaluate forest management strategies. The wood produced is divided according to its quality into different parts, among which the residue is used for energy. The dried wood chips are then gasified in a dual fluidized bed. The latter consists in two interconnected fluidized beds: one for gasification, one for char combustion. In the gasification part, sand is fluidized by a part of the produced syngas, in this part, dry wood chips are converted into gas, char and tar, plus some contaminants (NH3, HCl, ashes). Gas and char undergo some secondary reactions (mainly hydrocarbon cracking and water gas shift reactions). Char and soot undergo gasification reactions 4 . The dual fluidized bed can take different forms as described in Abdelouahed et al. 4 . Furthermore, one has to include the gas scrubbing, filtration, disposal of ashes, efficiency of the engine to produce electric current. All parts of the process have to be modeled, as well as the whole of the route. Different scales have to be considered: the largest concerns the forest, its management and the reactors. This can be included in a global system (e.g. in ASPEN Plus) allowing to develop a life cycle assessment of the route. This global program requires models for the different subparts: the fluidized beds, the scrubber, the filtration equipments, the engine, etc… We shall consider only the reactor in this work: the modelling of this equipment requires, beside hydrodynamics and heat transfer, the reaction thermodynamics and kinetics: the pyrolysis (this is the first part of each thermal reaction of pyrolysis), the different other reactions involved.

Production of valuable chemicals by hydrotreatment of lignin

Lignin is the second most important important polymer in ligno-cellulosic biomass 5 . It is a byproduct of the pulp and paper industry and is available at low prices. In this case, the biomass is separated into cellulose, hemicellulose and lignine, the later two being often considered as wastes.

Fig. 3 presents a possibility of a biorefinery Fig. 3: A possible ligno-cellulosic biorefinery (according Olcese et al. 6 ). OMACs: oxygenated mono-aromatic compounds.

Instead of burning the technical lignin produced this way, the possible route investigated in our team by Olcese et al. 6 , consists in depolymerizing the lignin to produce oxygenated mono-aromatic compounds, which then undergo a catalytic hydrogenation (HDO) to produce valuable aromatics (BTX).

SCALES INVOLVED

The simulation of the global route involves a number of scales (from the forest management to the engine via driers, scrubbers etc. Only the reactors will be considered here and even there, the scales involved are manifold.

The reactor scale

A detailed description of a reactor model of a dual fluidized bed gasifier can be found in Abdelouahed et al. 4 . A simplified scheme of the dual fluidized bed gasification reactor investigate by these authors is presented in Fig. 4.

On this figure, a number of reaction steps appear, that have to be considered separately. Part of these can be modeled using a commercial software (in this case Aspen+), part have been modeled separately (indicated as Fortran on Fig. 4). The design rules of the reactor, be it of a hydrogenation fixed bed or a gasification fluidized bed, require "global" kinetics which can be combined with hydrodynamics and transfer phenomena and which can be used for the global modeling of the reactor. These "global" kinetics have to be combined with local hydrodynamics (like it is developed for fluidised beds e.g. by the team of Kuipers 7 ). In case of HDO reactors, global information on the catalytic reaction kinetics (including the effects of external mass transfer to the particles, diffusion in the particles, poisoning) are required to determine the ideal catalyst particle size, the type of reactor (gas-solid or gas-liquid-solid, slurry, fixed or fluidize bed, cocurrent upflow or downflow) and its size. These global kinetics are often determined in so-called pilot plants and have to be combined with the flow behaviour of the reactor (e.g.in case of high pressure gasliquid-solid HDO taking into account maldistribution of the liquid as investigated by Llamas et al. 8 ).

The particle scale

Models of biomass particles pyrolysis, including heat and mass transfer and chemical kinetics, are developed in our laboratory. Particles are heated by specific devices with a controlled heat flux density (W/m 2 ) to mimic the thermal conditions of different reactors have been developed. A very efficient tool to this effect is the image furnace described in Christodolou et al. 9 . Fig. 5: Pyrolysis in a vertical image furnace (Christodolou et al. 9 ) Global kinetics of catalytic hydrogenation of tar surrogates are made in classical fixed bed reactors (see Olcese et al. 10 )

The micrometric scale

At this scale, the mesoscopic behaviour of the wood particles during pyrolysis is observed by a number of techniques: SEM and TEM microscopy (Fig. 6), rheology (Fig. 7), [START_REF] Gillenwater | Fuel and Chemical Products from Biomass Syngas[END_REF] H NMR, Thermogravimetric Analysis (TGA). These investigations prove clearly that during wood pyrolysis, a liquid-like intermediate is formed. These sticky, caramel like intermediates may interfere with fluidization hydrodynamics and a rigorous modeling of this part of the process is not yet possible.

The microscopic scale

Lignocellulosic biomass as well as its pyrolysis products are complex mixtures, and it is impossible to predict a priori the exact kinetics of the reactions happening, or even the complete mechanisms involved. For this reason, two approaches have been developed:

-implementing advanced in situ measuring techniques to detect not only the pyrolysis products, but also labile intermediates to develop a well funded model. This approach is exemplified by the work of Dufour et al. 12 . There a VUV-SPI source (synchrotron radiation) is coupled with a QTOF Mass spectrometer, allowing to detect the fragmentation products of different parts of biomass.

using "surrogates": the ideal surrogate would be either a pure component or mixture of a limited number of components presenting proprieties similar to that of the pyrolysis product considered. This "surrogate" technique has been applied successfully to the combustion of gasoline 13 and diesel oil 14 . In our group, guaiacol (1-methoxy-phenol) is used as a surrogate for lignin pyrolysis primary tars 15 . The kinetics of catalytic hydrogenation of guaiacol has been extensively studied and an original catalyst has been developed and the catalytic mechanism elucidated by Olcese et al. 15 . One point should however not be forgotten: even if all the relevant scales are investigated, the link between the different scales is not always possible. There is still a lot of work to do before being able to predict e.g. the effect of the change of one biomass to an other on the performance of a biorefinery or of a gasification system to produce heat and power.

CONCLUSION

Figure 1 :Fig. 2 :

 12 Figure 1: Different routes to upgrade different kinds of biomass (Gillenwater 1 )

Fig. 4 :

 4 Fig. 4 : Simplified scheme of a dual fluidized bed gasification reactor (Abdelouahed et al. 4 )

Fig. 6 :Fig. 7 :

 67 Fig.6: Wood char particles from mm to μm: bubbles formed at μm scale, even for slow pyrolysis(Dufour et al.,11 )

Figure 8

 8 Figure 8 summarized the different scales at which thermal conversion of lignocellulosic biomass is investigated in our group.

Fig. 8 :

 8 Fig. 8: work done in Nancy in the thermal conversion of lignocellulosic biomass


Christophe Huriaux
email: christophe.huriaux@irisa.fr

Antoine Courtay
email: antoine.courtay@irisa.fr

Olivier Sentieys
email: olivier.sentieys@inria.fr

Design Flow and Run-Time Management for Compressed FPGA Configurations

Keywords:

The aim of partially and dynamically reconfigurable hardware is to provide an increased flexibility through the load of multiple applications on the same reconfigurable fabric at the same time. However, a configuration bit-stream loaded at runtime should be created offline for each task of the application. Moreover, modern applications use a lot of specialized hardware blocks to perform complex operations, which tends to cancel the "single bit-stream for a single application" paradigm, as the logic content for different locations of the reconfigurable fabric may be different. In this paper we propose a design flow for generating compressed configuration bit-streams abstracted from their final position on the logic fabric. Those configurations will then be decoded and finalized in real-time and at run-time by a dedicated reconfiguration controller to be placed at a given physical location. Our experiments show that densely routed applications gain the most with a compression factor of more than 2× using the finest cluster size, but coarser coding can be implemented to achieve a compression factor up to 10×.

I. INTRODUCTION

FPGAs can be seen as a sea of logic elements glued together by a dense routing network assuring the data links. Because of the overhead needed by fully programmable logic elements to undertake the implementation of a complex function, FPGA manufacturers add heterogeneous resources in the circuit. These cells perform more efficiently specific tasks such as arithmetic calculations (multiplications, additions, etc.) signal processing or interfacing the chip with incoming and outgoing signals. Logic elements, as well as complex cells and routing network, can be electrically programmed thanks to memory cells tied to each transistor realizing a connection on the logic fabric. Although they are evenly positioned on the circuit, all of these memory cells can be seen as a single memory layer. This configuration memory is intended to receive a bit-stream, the set of each bit determining the state of every configurable element of the FPGA. This leads to increasing bitstream sizes, up to dozens of megabits.

Most bitstream compression techniques in the literature use a compression algorithm like LZSS [START_REF] Li | Configuration compression for Virtex FPGAs[END_REF] to reduce the bitstream redundancy and thus require some logic at runtime to decompress a given bitstream. Pan et al. [START_REF] Pan | Configuration bitstream compression for dynamically reconfigurable fpgas[END_REF] implemented such compression technique and also applied it to reduce the redundancy between multiple bitstreams. On the contrary, Stepien et al. [START_REF] Stepien | On feasibility of FPGA bitstream compression during placement and routing[END_REF] introduced a technique to optimize the logic resources organization during the placement phase in order to reduce the distribution of these resources, which reduce the number of configuration bits required for a given task.

In this paper we introduce the Virtual Bit-Stream (VBS) coding format allowing to abstract the conventional bit-stream from the underlying routing architecture and to provide fast relocation capabilities. A Computer Aided Design (CAD) flow associated with the generation of such bit-stream format is proposed. We also define an architecture relying on a reconfiguration controller to decode and decompress at runtime these VBSs to generate FPGA configurations depending on their physical locations. The paper is organized as follows. Section II introduces our concept of VBS, discusses the novelty of the solution and presents the general architecture associated with the flow. In Section III, we describe the design flow used to generate the VBS using the VTR framework. Experimental results are presented in Section IV where we compare the size of our Virtual Bit-Stream to a raw bit-stream. Section V concludes this paper and proposes some perspectives of this work.

II. CONCEPT OF VIRTUAL BIT-STREAMS

A. Architecture

The architecture that we use to evaluate our design flow is similar to the island-style architecture used by the Xilinx Virtex circuits. The logic fabric is seen as a sea of logic blocks (LBs) distributed on a grid. The interconnection network is a mesh routing network made of single length routing wires (i.e. each wire interconnects one element of the grid with one of its neighbors). We assume that the basic logic blocks of this FPGA architecture are made of 6-input Look-Up Tables (6-LUT) associated with a flip-flop. In the standard model used by the place-and-route software used in our design flow, Versatile Place and Route (VPR) [START_REF] Betz | VPR: A new packing, placement and routing tool for FPGA research[END_REF], the inputs and outputs of the circuits are spread on the sides of the logic fabric. However, for our experiments and in the context of dynamic reconfiguration, we will consider these inputs and outputs as part of the heterogeneous logic fabric itself.

The mesh routing network can be split into multiple elements repeated over the reconfigurable fabric to form the interconnection network. As shown in Figure 1.a, horizontal (ChanX) and vertical (ChanY) routing channels (in green) make the connection between the LBs and the routing network. A switch box (in red) is placed at the intersection of ChanX and ChanY to complete the mesh routing network.

B. Virtualization

The goal of our design flow is to produce virtualized bitstreams, which are abstracted of their final placement on the logic fabric. The process of virtualization consist in removing the inner details of the hardware task routing and to only describe its interconnection at a higher level. The virtualization process can be operated at various levels of granularity. At the finest granularity we only consider one logic element of the logic grid and its surrounding routing, consisting of the Fig. 1: (a) Detailed view of a macro (b) Routing in a macro horizontal (ChanX) and vertical (ChanY) connection boxes adjacent to the logic element and one switch box interconnecting both connection boxes. These four elements together form a macro, the simplest building block of our logic fabric which can be replicated in both the horizontal and vertical axis to build a variably sized reconfigurable fabric.

If we consider the macro depicted in Figure 1.a, the routing channels consist of W tracks connected to L inputs or outputs of the surrounding logic blocks. The switch box of the macro also connects the ChanX and ChanY together. The programmable switches of this macro are either made of pass transistors, tri-state buffers, or a combination of both. A 4-way (cross-shaped) interconnection switch will be implemented with up to six of these programmable switches, while a 3-way (T-shaped) switch will need three programmable switches. In addition to the configuration of the routing structure, the data stored into the logic elements (e.g. the LUT content or the configuration of a hardware block) also adds up to the count of required programmable bits in the configuration bit-stream.

The number of programmable switches is defined by

N raw = N LB + 6 × [N S + N C+ ] + 3 × N CT , (1)
where N LB is the size of the configuration of the logic block, N S is the number of configurable switches in the switch box, N C+ is the number of 4-way (cross-shaped) configurable switches per channel, and N CT is the number of 3-way (Tshaped) configurable switches per channel. For our architecture consisting of only 6-LUT logic blocks with a flip-flop (i.e. a logic block with 7 inputs/outputs), N LB = 2 6 + 1 = 65, N C+ = 7 × (W -1) = 28 and N CT = 7. All these programmable switches add up to N raw = 284 in total for a single macro with five routing tracks. Each of these programmable switches will need one bit of configuration in the bit-stream of this hardware task. Our approach relies on the fact that the routing density varies among the surface of the reconfigurable fabric used by a considered task. The number of configuration elements in the bit-stream remains the same, although their state is set accordingly to the task to perform. The virtualization operation aims to represent the routing part of the macro in another format, smaller than the N raw = 284 bits required to describe the full bit-stream.

In the example given in Figure 1.b, a macro with W = 5 tracks contains four routes. The routing network of this macro can be abstracted into a black box where each input and output of the black box is a connection to the surrounding routing channels or logic blocks. Each of these inputs and outputs is assigned an input/output (I/O) number which uniquely represents the I/O across the macro. The VBS corresponding to this macro contains only a list of the connections coded 1, M is equal to 5, which means that we can code up to ⌊ Nraw 2M ⌋ = 28 connections until we reach the point where the compression is not beneficial anymore. The final VBS is made of a header containing the hardware task metadata (e.g. its size, the number of macro) and of the list of macros coded using the aforementioned techniques. Table I describes the VBS binary format and the metadata associated with it. w and h denotes respectively the width and height of the hardware task. L is the number of inputs and outputs associated with the logic block of a given macro.

C. Runtime controller

At runtime, the VBS requires an additional decoding step in order to generate a raw configuration bit-stream compatible with the target reconfigurable fabric, as shown on the overview of the architecture in Figure 2. This figure features an external memory containing the VBSs corresponding to each task being loaded and de-virtualized by the reconfiguration controller prior to their insertion on the logic fabric. In order to keep the online decoding step as easy as possible, most of the complexity is off-loaded on the coding part of our design flow, performed offline. As such, the offline part of the flow makes sure that the generated Virtual Bit-Stream will be able to be decoded during the online part, by running the same algorithm and re-ordering the connection lists if necessary.

The de-virtualization algorithm implements a simple router. The VBS data is processed macro by macro and the connection list is expanded in a in-memory macro configuration representing the part of the final bit-stream corresponding to this element of the reconfigurable fabric. Since it is operating at the level of a single macro, the de-virtualization process can be easily parallelized to process multiple macro at once and thus to accelerate the decoding of a VBS. This runtime controller could be implemented and adapted to any reconfigurable fabric. However, the absence of specifications of the bitstream format for commercially available FPGA architectures prohibits its use on widely used reconfigurable circuits. For the purpose of our experiments, the whole Computer Aided Design

III. CAD IMPLEMENTATION

A. VTR Tool-Flow

The design flow associated with the generation of VBS, depicted in Figure 3, relies on the Verilog-To-Routing (VTR) [START_REF] Rose | The VTR project: architecture and CAD for FPGAs from verilog to routing[END_REF] tool flow. This synthesis framework implements most of the required parts of our CAD flow from the hardware description synthesis to the generation of placement and routing data using the Versatile Place and Route (VPR) [START_REF] Betz | VPR: A new packing, placement and routing tool for FPGA research[END_REF] software.

Our design flow accepts a hardware description as an input and generates a VBS according to several architecturedependent parameters (e.g. the channel width, the LUT size) used offline. Although VTR was originally designed for academic purposes as a open-source synthesis framework for the community, some recent initiatives, such as RapidSmith [START_REF] Hung | Escaping the academic sandbox: Realizing VPR circuits on Xilinx devices[END_REF], were proposed to connect VTR to commercial Xilinx FPGA. We presently use VTR to generate a partial implementation of the considered FPGA circuit. The result is a synthesized, placed, and routed hardware task fed into our custom VBS generation backend. The VTR part of our design flow could be replaced by any other framework generating similar data.

B. VBS Generation Backend

In contrast to the raw upstream data generated by VTR, our VBS generation software vbsgen outputs a usable VBS ready to be loaded onto the target platform. Vbsgen uses the placement, routing and netlist data obtained from VPR in conjunction with a detailed software model of the reconfigurable architecture to generate the final VBS. The architecture model overlaps with the one used by the VTR framework as it describes the composition of the logic grid of the reconfigurable fabric as well as the structure of the interconnection network of the circuit. Additional data is included in the vbsgen model for the bit-stream generation operation: detailed information on the routing structure and methods to serialize the logic block data are required in addition to what is already present in the VTR architecture.

Internally, vbsgen builds a usable description the target reconfigurable architecture in memory using its model and parameters passed at runtime (e.g. number of tracks in a channel, size of the LUTs). This internal model needs to be thoroughly defined since every slight difference between the VTR architecture, the vbsgen architecture model, and the target architecture can lead to the generation of invalid bitstreams. As stated in Section II-C, vbsgen is responsible for the generation of valid bit-streams that the online controller will be able to decode at runtime. To enforce this behavior and ensure that the online decoding will meet the requirements, the devirtualization algorithm used online is implemented in software and included in a feedback loop during the offline generation of the VBS. Because of the stateful nature of the decoding algorithm, the order of the connections in the connection list of each macro has an important impact on the success of finding a valid routing online. As such, if a generated VBS is proven non-routable by the feedback loop, the connections are reordered to find a non ambiguous order. In the end, if no feasible connection list is found, the raw coding of the considered macro is included in the VBS instead of the smart connection list. This fallback behavior can induce lesser compression gains but guarantees that the hardware task will be handled correctly in all cases during the online placement.

IV. EXPERIMENTAL RESULTS

In this section we evaluate the effects of the VBS described in Section II, using the general architecture introduced in Section II-A. The logic blocks contain a 6-input LUT associated to a flip flop. We used a set of the 20 largest benchmarks from the MCNC circuit suite [START_REF] Yang | Logic synthesis and optimization benchmarks user guide: version 3.0[END_REF] to test our design flow, listed in Table II. Of these 20 benchmarks, 13 of them contain over a thousand logic blocks. These benchmarks where packed into 6-LUT logic blocks and synthesized using VPR. We let VPR perform its routing using the minimum channel width guaranteeing a feasible routing, as indicated in the MCW column of Table II. In order to make a comparable analysis of these benchmarks together, we normalized these circuits with a channel width of 20 tracks during the generation of the raw bit-streams and the Virtual Bit-Streams. The following subsection studies the compression induced by the Virtual Bit-Stream coding. In subsection IV-B, we analyze the effect of the the VBS at a coarser grain.

A. Bit-Stream Compression

As stated in previous sections, the abstract coding of the VBS allows to reduce the storage space footprint of a considered hardware task in comparison to a raw bit-stream. Figure 4 depicts the results of the coding of the 20 MCNC benchmarks into a raw bit-stream (BS) and a Virtual Bit-Stream (VBS). A logarithmic scale is used on the size axis because of the high variance in term of logic area of the benchmark circuits.

We observe an average compression ratio of 41% of the raw bit-stream size over the 20 circuits using our VBS coding. The VBS coding is especially efficient in sparse macro of the circuits where the routing network is not fully used, whereas congested locations see little to no enhancement over the bit-stream size. Overall, the VBS performs constantly better in terms of size in comparison to the raw coding. In the eventuality where the VBS coding would be bigger than the raw one, it would be possible to simply use the raw coding of the most congested macro of the circuit in order to still be at least as good as the original bit-stream.

B. Virtual Bit-Stream Clustering

The examples introducing the VBS in Section II assumed the finest possible grain of coding in the context of our work: one logic block, surrounded by its local routing. It is also possible to use a coarser grain for the routing abstraction, by clustering multiple macros together. This aggregation allows to pool the routing resources of the cluster and thus to provide a higher level of abstraction, at the cost of increased computing needs at runtime to perform the online de-virtualization of the VBS.

Figure 5 depicts the results of the bit-stream creation of the 20 MCNC benchmarks on the same architecture used for the compression comparison. The cluster size is expressed in terms of number of macros per square side of the cluster, as we only consider regular square clusters. A cluster of size 2 thus aggregates 4 macros together. For each cluster size, the minimum and maximum values of the VBS size of the 20 benchmarks is given by the error bars, along with the geometric mean of this size across the benchmark suite. An additional indicator presents the average value of the compression ratio as a percent of the original raw bit-stream size. As shown by Figure 5, the clustering has a important effect on the compression ratio which decreases from 41% to 9%-15% of the original raw bit-stream size for superior cluster sizes. It shall be noted that although going from no clustering at all to clusters of size 2 increases the compression by a factor of 4×, higher sizes of clusters shows less benefits and can be even worse in terms of bit-stream size, while needing higher computing power to decode.

V. CONCLUSIONS AND FUTURE WORK

This paper presents a design flow for generating compressed configuration bit-streams abstracted from the lowerlevel routing details of the reconfigurable architecture and from their final position on the reconfigurable fabric. The VTR framework has been expanded to include bit-stream generation features. A bit-stream format is proposed to take part of our approach and the associated architecture was presented. We analyzed the compression induced by our coding method and proved that compression ratios of at least 2.5× can be achieved on the 20 largest MCNC benchmarks. The introduction of clustering which aggregates multiple routing resources together showed compression ratio up to a factor of 10×, at the cost of a more complex decoding step at runtime. Future perspectives on the VBS include extension of the architecture to support commercially available FPGAs as well as the improvement of the associated CAD tool flow to include smarter coding of the VBS to gain in runtime efficiency and in size. The VBS approach can provide increased online relocation capabilities thanks to a decoding algorithm capable of decoding the VBS on-the-fly during the task migration.

Fig. 3 :

 3 Fig. 3: CAD flow of the Virtual Bit-Stream (CAD) flow was developed in the context of the architecture described in Section II-A.

Fig. 4 :Fig. 5 :

 45 Fig. 4: Comparison of the size of raw bit-streams and Virtual Bit-Streams

TABLE I :

 I

Virtual Bit-Stream format Fig. 2: Overview of a typical Virtual Bit-Stream architecture on M = ⌈log 2 (4 * W + N logic IO )⌉ bits. In our example architecture of Figure

TABLE II

 II

	: Benchmark set used (MCW: Minimum Channel
	Width) (LB: Logic Block)

ACKNOWLEDGMENT This research is sponsored by the European Commission under the 7th Framework program within the FlexTiles project (FPT ICT-288248) and by the French Ministry of Research.