Benoît Pradelle
email: pradelle@icps.u-strasbg.fr

Alain Ketterlin
email: ketterlin@icps.u-strasbg.fr

Philippe Clauss
email: clauss@icps.u-strasbg.fr

Transparent Parallelization of Binary Code

This paper describes a system that applies automatic parallelization techniques to binary code. The system works by raising raw executable code to an intermediate representation that exhibits all memory accesses and relevant register definitions, but outlines detailed computations that are not relevant for parallelization. It then uses an off-the-shelf polyhedral parallelizer, first applying appropriate enabling transformations if necessary. The last phase lowers the internal representation into a new executable fragment, re-injecting low-level instructions into the transformed code. The system is shown to leverage the power of polyhedral parallelization techniques in the absence of source code, with performance approaching those of source-to-source tools.

INTRODUCTION

Due to the physical limits recently reached, improvements in processors' clock speed has been stopped. Processors manufacturers are now concentrating on increasing the number of cores on processors, putting an important pressure on parallelism extraction. Many automatic parallelization techniques have been proposed in the past few decades. A vast majority of those concentrate on parallelism extraction from source code; however in many cases it is interesting to consider parallelizing applications after their compilation, at the binary level. This approach allows one to handle any application independently from its source language, even if the source code has been lost (legacy code) or if the source code is not distributed (closed source software). Moreover with this approach, the whole application can be parallelized, including libraries. Thus, the presented solution can be implemented as an OS service, able to automatically parallelize any binary application, typically during its installation.

Analyzing a binary application can be a complex task: it might be difficult to extract even a simple control flow in some cases. One could propose to wait for the runtime to benefit from a totally determined execution context and perform an exact analysis. However we observed that it is rarely needed in practice: static analysis is enough for most of the binary codes and does not suffer from overheads induced by dynamic techniques.

To perform an efficient parallelization, binary code needs to be raised to some more suitable representation. Typically, one could think of some classical compiler intermediate representations such as the LLVM [START_REF]The LLVM compiler infrastructure[END_REF] or GCC ones. However those representations are usually unsuited to describe assembly code as is (with non-typed data, one unique array to represent the memory, ...). Moreover using an internal representation imposes to implement the needed parallelization strategies for this specific representation. We have chosen to use C code as intermediate representation and only raise a small subset of the code semantic. Source to source parallelizers working with C code can then be used to obtain a parallel intermediate form, into which the detailed semantic is restored and then compiled to obtain a parallel executable.

We concentrate on extracting loop nests fitting the polytope model in order to benefit from the powerful transformations performed in this model.

The basic architecture of our system is shown on Figure 1. First, the binary code of the program is parsed and transformed into an intermediate representation whose concrete syntax is C. Second, the resulting C code is submitted to a parallelizing compiler, whose role is to detect parallel loops and which is free to apply any program transformation. Third, the resulting parallel code is transformed back into executable code, and embedded in a lightweight run-time component that is responsible for replacing original regions of code with new, optimized ones.

EXTRACTING PARALLELIZABLE REGIONS FROM BINARY CODE

The first phase consists in parsing the binary code of the program, extracting one routine at a time, and building a control-flow graph (CFG) for the routine whenever possible. Indirect branches are tentatively solved by scanning jump tables; no optimization will ever be attempted on routines where the CFG is not fully recovered. After the dominator tree is computed, a loop hierarchy is reconstructed using DJ-graph [START_REF] Sreedhar | Identifying loops using dj graphs[END_REF] based techniques (irreducible loops are "solved" by replicating parts of their bodies). At the end of this phase, every loop has a unique entry block, a set of local basic blocks, and a set of sub-loops. Note that loops are reconstructed as they appear in the binary, and no refactoring takes place. If the compiler has unrolled and/or peeled some iterations, the full scope of the loop may not be recovered. We have left such refactoring for future research.

The next step is to perform a data-analysis of the program, by putting it into static single assignment (SSA) form. This gives a unique version number for each register definition, and provides a direct use-def link for each register usage. All registers are tracked, and memory is handled as a weakly updated variable (where each memory write explicitly refers to the currently visible version). Starting from every memory access, and "slicing back" through use-def links, it is possible to reconstruct the computation of the memory access' address.

The slicing proceeds while the reconstructed function is linear, and until meeting either a memory access that cannot be resolved, or an input register (i.e., a routine parameter), or a φ-function. The result is a linear combination of registers. Whenever a φ-function appears in a memory access function, an induction-variable resolution procedure tries to express it as a linear function of a newly introduced normalized loop counter, and in cases where this succeeds the register is replaced by the resulting expression. In many cases, this sequence of steps is enough to express all memory accesses inside one or more loops as linear expressions involving loop counters and loop-invariant registers, all with integer coefficients.

Similarly, branch conditions are tentatively expressed as linear expressions compared to zero with <, ≤ or = (and their negations). Combined with control dependence (which can be computed from the CFG) on blocks that may exit the various loops involved, one can compute loop "trip-counts" or, more precisely, symbolic constraints on blocks inside loops. Here again, these constraints involve linear combinations of loop counters and loop-invariant registers: they are used later as guards when generating C code from the binary, and also by the parallelizing compiler to decide which polyhedral transformation to apply. Before that, a final slicing step starts from all linear expressions involved (in memory accesses and branch conditions) and selects which instructions from the original program are still necessary: these instructions are then "outlined" and replaced with abstract statements that hide all the architecturespecific intrinsic computations. What remains is a pro-

PARALLELIZING THE C CODE

After the code extraction described in previous section, we obtain a C code made of all the memory accesses performed in the binary code but where the semantic is hidden. We do not want to restore the code semantic here in order to keep the code as simple as possible for polyhedral tools later transforming this code. Figure 2 presents the C code as extracted from a binary matrix multiply. The computation is made in register xmm1 before being written back to memory, represented by the M array. Note that the operations on values have all been replaced by a generic operator ⊙, this operator can be implemented by any operator in the C code used by the transforming compiler, + for example. As is, this code fits the polytope model requirements. However, most modern polyhedral compilers fail to take such codes into account, for two main reasons. First, the large values used as coefficients in linear functions often lead to internal errors. Those coefficients are actually due to the linearization of the access functions and to our representation of the memory as an array which base is at address zero. Splitting the memory into arrays solves this problem. Second, the scalar values xmm0 and xmm1, which are only temporary variables, add some extra dependencies which prohibit many transformations in the polytope model. Those scalar references can be removed in some specific cases.

Splitting the memory

To help the parallelizer, we simplify memory accesses by splitting non-intersecting memory areas into different arrays and by rebuilding multi-dimensional arrays whenever it is possible. If the loop bounds are nonparametric, those dimensions can be built back by checking all the possible array shapes. In the case of parametric loop bounds, rebuilding the arrays becomes complex and can be solved for some, hopefully common, parameter values in association with a runtime check.

Removing scalar references

A reference to a scalar variable in a polyhedral loop kernel can have a major impact on data dependencies but existing parallelization tools are currently poorly simplifying those scalar references: they actually expect those simplifications to have already been performed. However, in some cases, removing scalar references is not an easy task.

The first technique which can be applied is forward substitution. One can see in figure 3 the matrix multiply code after forward substitution. Even if references to xmm0 have been suppressed, some references to xmm1 remain. Some compilers implement privatization to solve those remaining cases but privatization seems difficult to implement in the polytope model and this support appeared to be broken in PLuTo [START_REF] Bondhugula | A practical automatic polyhedral program optimization system[END_REF][START_REF]PLuTo website[END_REF] and PoCC [START_REF] Pouchet | Iterative optimization in the polyhedral model: Part II, multidimensional time[END_REF][START_REF] Pouchet | Iterative optimization in the polyhedral model: Part I, one-dimensional time[END_REF] during our tests. Another commonly suggested transformation is to use results about scalar expansions, contraction and renaming [START_REF] Lefebvre | Automatic storage management for parallel programs[END_REF][START_REF] Thies | A step towards unifying schedule and storage optimization[END_REF]. However, no tool is currently able to perform both transformation and memory space optimization efficiently. Moreover, guiding the transformations according to the memory space used by expanded variables is also a complex task. To illustrate it, we present in figure 4 the matrix multiply code, transformed by PLuTo after expanding xmm1. One can see that no contraction is possible anymore once the code has been transformed, leading to memory space and performance penalties. Another solution would be to perform some pattern matching on some specific data flows. In the example from figure 3, we could identify that, before and after . This strategy would be easy to implement and would probably lead to decent results. However, we could not guarantee that it could remove every scalar references. Applying this strategy could lead to a code equivalent to the classical matrix multiply as presented in figure 5.

Notice that those scalar variables can be suppressed only if we can determine which value they hold after the loop nest. In our example, we may initialize the scalar variable xmm0 with A1

Transformations and parallelization

The resulting C code can be parallelized using any sourceto-source parallelizing compiler. There is theoretically no restriction on which transformations can be performed by the parallelizer. In our implementation we only prohibit the compilers to fuse or split statements in order to ease the next step. Our implementation currently uses PLuTo [START_REF] Bondhugula | A practical automatic polyhedral program optimization system[END_REF][START_REF]PLuTo website[END_REF] as a backend parallelizer. This genericity allow our method to benefit from any future developments in code optimization techniques. As we can use any source-to-source compiler, there is also no need for reimplementing existing techniques specifically in our system.

MERGING THE PARALLEL CODE 4.1 Recovering the semantic

The code used as input for the parallelizing backend is made of the correct memory accesses but is semantically wrong. The correct semantic is actually defined by the binary code statements. We identify which statements in the binary code maps to the statements in the parallel C code. To achieve this, we use a PLuTo specific behavior: this compiler numbers the statements in order of appearance in the input sequential code. In other compilers other information could be used like line numbers in the input code usually maintained during the compilation for debugging purposes.

Once the mapping between instructions in the binary code and instructions in the transformed parallel code is found, we can replace statements by inline assembly made of the original statements' code. The original assembly code is not directly injected: some registers or memory accesses have been replaced by linear expressions when extracting the code. Those expressions are evaluated in pure C code before being used in assembly instructions. We also replace SIMD instructions by SIMD intrinsics. Another specificity is that the hardware registers are mapped to C variables in the generated code. Thus, inlined assembly never refers to a specific hardware register but to C variables only. This reduces the constraints on the register allocator of the final C compiler and simplifies code generation.

Figure 6 presents the final code after transformation, parallelization, and semantic restoration. In the presented resulting code, we have used PLuTo to perform the polyhedral transformations, handling scalar values through privatization, manually ensuring that the result is correct. We can observe the SIMD registers used as variables, inline assembly, and SIMD intrinsics. The parallelization is achieved through simple OpenMP pragmas.

Re-injecting the new code in the application

To finalize the code generation, those transformed loop nests must now replace their sequential counterparts in the application. The transformed loop nests are compiled as different functions of a dynamic library, which is loaded using OS facilities when the application starts. Just before the main function call, a runtime component, automatically generated by our tool-chain, inserts breakpoints at loop entries in the sequential application. When those breakpoints are met, the runtime compo- nent redirects the execution flow to the corresponding transformed loop nest. This runtime component also communicates the value of hardware registers to the new loop nest in order to link the variable representing those hardware registers to their actual values. After the transformed loop nest execution, the runtime component writes the value of hardware registers variables back to the actual registers before redirecting the execution flow to the end of the original loop nest. This mechanism ensures the smooth transition between the original code and the transformed loop nests.

FIRST RESULTS

We have implemented most of the framework described in this paper and present in this section some preliminary results that we measured. The scalar replacement step, occurring after the code extraction from the binary code and before its transformation by a polyhedral compiler, has not yet been implemented. In the presented results, it has been performed by hand. The benchmarks used have been taken from the Poly-Bench [START_REF]PolyBench website[END_REF] benchmark suite. Codes have been compiled by GCC 4.4.5 using the -O2 optimization flag on a recent Linux system. Those codes have been executed on an Intel Xeon W3520 with four processor cores and two threads per core.

Code coverage

Our system was able to detect all the loops and to transform a vast majority of them in the tested codes. Some loop nests have not been parallelized by our system because of function calls in the loop body: we conservatively ignore the loop nest in that case. We plan to implement a mechanism such as inlining or interprocedural analysis to handle more loop nests. The encountered function calls were often destined to mathematical functions which do not perform any write operations on memory; we then expect good results from such mechanisms. We present in figure 7, the number of detected loop nests compared to the number of loop nests in the source code. We can see a current average coverage of 83.5% of the loops actually present in the source code.

Runtime overhead

Our current implementation uses the Linux ptrace mechanism to redirect the execution flow from the original code to the parallel loops. This has obviously an impact on performance, linearly depending on the number of redirections. We measured this overhead to be around a tenth of milliseconds per loop nest execution on our test platform. It means that, in order to obtain speedup, the parallelization must lead to an execution time gain bigger than a tenth of milliseconds, which seems quite reasonable.

Raw performance evaluation

We present in figure 8 an overview of our system performance. One can see the speedup over the sequential version of each code when parallelized from the source code using PLuTo (denoted source in the figure) or when using our system (denoted binary in the figure).

We can see that our system can reach speedups comparable with the ones resulting from a source code parallelization. Note that most of the benchmarks in this suite have sequential execution times around a second. This causes the runtime overhead to become quite significant when measuring our system performance. The slight difference between the source code and the code extracted from binary applications is the cause of most of the performance gaps as they often induce important differences in the parallel schedule generated.

The atax program illustrates the source code sensitivity of PLuTo. Some differences appear in the extracted code compared to the original source code. For example, some parameters in the source code become constant values in the binary codes. Such changes seem to provoke different transformations, leading to different performance. In the case of atax, this performance gap is favorable to the source code version.

With 2mm, one can see that our system significantly outperform the source code parallelization. This is due to an error induced by the source code parallelization: if the tiling is activated in PLuTo, the program does not terminate normally. We then deactivated tiling when parallelizing the source code of this particular program, leading to a poor performance of the source code parallelization.

One can also see that our system fails to generate an efficient parallelization of gramschmidt. In this particular program, the main computation loop nest contains a call to the mathematical library, currently prohibiting the transformation of this loop.

RELATED WORKS

Polyhedral loop transformation is now a well established theory and many tools exist to perform parallelization and transformations in this model such as PLuTo [START_REF] Bondhugula | A practical automatic polyhedral program optimization system[END_REF][START_REF]PLuTo website[END_REF] or PoCC/LetSee [START_REF] Pouchet | Iterative optimization in the polyhedral model: Part II, multidimensional time[END_REF][START_REF] Pouchet | Iterative optimization in the polyhedral model: Part I, one-dimensional time[END_REF]. Those tools provide parallelization from source to source, usually C or FORTRAN programs can be handled.

Many tools like PIN [START_REF] Luk | Pin: building customized program analysis tools with dynamic instrumentation[END_REF] or DIABLO [START_REF] Van Put | Diablo: a reliable, retargetable and extensible link-time rewriting framework[END_REF] provide some facilities to analyze, transform, and, for some of them, create a new transformed application. Our work can be considered as a specific usage of such frameworks and could have been implemented using anyone of them.

From our knowledge, only two recent papers present a solution to binary code parallelization. First Yardımcı and Franz have proposed a dynamic system to vectorize and parallelize a binary code [START_REF] Yardımcı | Dynamic parallelization and mapping of binary executables on hierarchical platforms[END_REF]. They are focused on loops or recursive functions with no dependence, which limits the scope of applicability of their system. They do not perform any loop transformation and the dynamic approach is not well suited to heavy transformations as polyhedral ones which require long compilation times.

Second, Kotha et al. proposed a framework [START_REF] Kotha | Automatic parallelization in a binary rewriter[END_REF] similar to the one described in this paper with a few significant differences. First, the analysis of the binary application they perform can only find loops and memory accesses that follow a restrictive pattern, reducing the scope of loops that can be parallelized. They decide whether to parallelize or not using non-exact dependence testing and do not perform any loop transformation. Our analysis does not have those restrictions: we perform a state of the art dependence analysis, we are able to perform loop transformations, and our use of C code as intermediate representation allows us to avoid re-implementing existing compilation techniques.

PERSPECTIVES

Using a polyhedral parallelizer in our system has revealed some weaknesses in supporting scalar variables by polyhedral tools. Currently, those tools expect codes where the temporary scalars have been suppressed. However this removal is not always straightforward. We plan to implement an automatic scalar removal pass in our tool in order to help the parallelizing compilers.

As our intermediate representation is a valid C program, any source-to-source optimizer can be used, making it possible to extend advances in compiler construction to binary applications with nearly no implementation cost. Among all the possible backends, one could imagine to apply vectorization or speculative parallelism for example.

In the current implementation, the extracted C code is focused on memory accesses for data dependence analysis. Nothing prohibits the construction of C code focused on other features like control flow for example, allowing backends to target other kinds of optimizations.

CONCLUSION

We propose a framework able to transform and parallelize binary codes using polyhedral transformations. Partially raising the binary code to C code allows it to use any source to source tool to transform or parallelize code with nearly no implementation cost. First results show that speedups similar to those obtained with source parallelization can be expected. Its efficient anal- ysis enables it to detect and handle most of the loops in binary codes, despite the optimizations performed by the original compiler.

Figure 1 :

 1 Figure 1: The system's architecture

Figure 2 :

 2 Figure 2: Matrix multiply as it is extracted from the binary code

Figure 3 :

 3 Figure 3: Matrix multiply after forward substitution

#Figure 4 :

 4 Figure 4: Matrix multiply after expansion and transformation

Figure 5 :

 5 Figure 5: Matrix multiply after scalar removal.

  [1023][8*1023] * A3[1023][8*1023] and xmm1 with A2[1023][8*1023].

Figure 6 :

 6 Figure 6: Matrix multiply after transformation by PLuTo and semantic restoration.

Figure 7 :

 7 Figure 7: Number of loop nests parallelized by our system compared to the number actually present in the source code.

Figure 8 :

 8 Figure 8: Speedup of each code when parallelized from the source code or by our system.


Remi Vieux

Jenny Benois-Pineau •

Jean-Philippe Domenger

Achille Braquelaire

Segmentation-based Multi-Class Semantic Object Detection

Keywords: Object Detection, Segmentation, Relaxation Labelling, Late Fusion, SVM

In this paper we study the problem of the detection of semantic objects from known categories in images. Unlike existing techniques which operate at the pixel or at a patch level for recognition, we propose to rely on the categorization of image segments. Recent work has highlighted that image segments provide a sound support for visual object class recognition. In this work, we use image segments as primitives to extract robust features and train detection models for a predefined set of categories. Several segmentation algorithms are benchmarked and their performances for segment recognition are compared. We then propose two methods for enhancing the segments classification, one based on the fusion of the classification results obtained with the different segmentations, the other one based on the optimization of the global labelling by correcting local ambiguities between neighbor segments. We use as a benchmark the Microsoft MSRC-21 image database and show that our method competes with the current state-of-the-art.

Introduction

The object detection and categorization aims to extract two kinds of information from the images: which objects are present in the image and where exactly are those objects located. The detection is closely linked to the task of object segmentation. One of the difficulties of object segmentation is to extract complex, highly structured objects composed of regions visually dissimilar. On the other hand, the recognition of objects is affected by several problems: low quality of images, partial occlusions, visually heterogeneous object categories, cluttered background, . . . The discrepancy between the low level features that can be extracted from the images and the high level semantic interpretation of images is known as the semantic gap [START_REF] Smeulders | Content-based image retrieval at the end of the early years[END_REF]. Many research efforts have been carried in the task of global image recognition such as scene classification [START_REF]Columbia university/vireo-cityu/irit trecvid2008 high-level feature extraction and interactive video search[END_REF][START_REF] Gokalp | Scene classification using bag-of-regions representations[END_REF][START_REF] Peng | Peking university at trecvid 2008: High level feature extraction[END_REF], but object recognition remains a challenge. This task is even more ambitious when multiple objects are present in the images.

One of the earliest work closely linked to the object detection and recognition topic was proposed by Duygulu et al. [9]. In this work, the authors address the recognition problem as the process of attaching words to image segments considering the task as a translation between one language (English words) to another (visual words, or blobs). A mapping between the keywords and the visual blobs is performed using a method based on Expectation Maximization. The rest of the literature [START_REF] He | Multiscale conditional random fields for image labeling[END_REF][START_REF] Shotton | Textonboost for image understanding: Multi-class object recognition and segmentation by jointly modeling texture, layout and context[END_REF][START_REF] Verbeek | Region classification with markov field aspect models[END_REF][START_REF] Galleguillos | Object categorization using co-occurrence, location and appearance[END_REF]2] noticeably differs from the original work by Duygulu et al. in the sense that the models built try to exploit the maximum of information that can be extracted from the image: not only low level features (color, texture, etc.), but also local contextual relationships between pixels or image segments, location and even global relevance estimates. He et al. [START_REF] He | Multiscale conditional random fields for image labeling[END_REF] proposed a pixel-wise labelling into a finite set of labels using a multiscale conditional random field formulation(mCRF). The mCRF combines the output of a local pixel-wise classification, a representation of the local geometric relationships between the objects and global label features into a probabilistic framework, trained using supervised labeled image data. Shotton et al. [START_REF] Shotton | Textonboost for image understanding: Multi-class object recognition and segmentation by jointly modeling texture, layout and context[END_REF] introduced a new approach for learning a discriminative model of object classes based on texture, layout and context information. Their model is based on texture-layout filters, a feature which jointly model patterns of texture and their spatial layout. Texture layout filters are combined with lower level image features (color, location) into a Conditional Random Field to provide a high-level discriminative model. They also discuss an efficient learning method of the CRF parameters based on boosting and piecewise training method. Verbeek and Triggs [START_REF] Verbeek | Region classification with markov field aspect models[END_REF] point out that Markov Random Field and aspect models such as Probabilistic Latent Semantic Analysis and Latent Dirichlet Allocation are complementary methods which attempt to improve the coherence of the labellin of image patches. MRF provides crisper local labelling by exploiting neighbourhood-level couplings while PLSA and LDA use global relevance estimates. They studied two spatial extensions of the aspect models, one based on a forest of minimal spanning trees and the other one on a regular 8-neighbor MRF. Galleguillos et al. [START_REF] Galleguillos | Object categorization using co-occurrence, location and appearance[END_REF] have shown that introducing contextual information about the co-occurrences and the relative location of image regions with local appearance-based features improves the global labellin. Athanasiadis et al.

[2] define a framework for simultaneous image segmentation and object labellin operating at the semantic level. They represent the contextual information as an ontological taxonomy of the set of possible semantic labels and employ fuzzy algebra to adjust the labelling of the regions given by region growing segmentation algorithms.

Our approach has been inspired by the notion of superpixels in image segmentation given by Ren and Malik [START_REF] Ren | Learning a classification model for segmentation[END_REF]. As opposed to pixels which are an unnatural arbitrary grid sampling of an image into a very large number of entities, superpixels provide a larger, locally homogeneous and coherent regions that preserve most of the structure necessary for accurate segmentation. We take up the idea that an image over-segmentation is sufficient to perform efficient recognition of small objects or object parts. The visual descriptors extracted at the region level are statistically more robust to noise than descriptors extracted at the pixel level. We will show that a Support Vector Machine classifier trained in an appropriate descriptor space for representing the segments already yields reasonable performances. A similar approach of using image segments was proposed by Hoeim [START_REF] Hoiem | Geometric context from a single image[END_REF] for the recovery of geometry context from single images. Yang et al. integrated appearance based classification of meanshift patches, a bag-of-keypoints model and global shape based Elliptical Fourier descriptors within a unified framework for object-based segmentation. Gould et al. proposed to combine appearance-based features computed on superpixels patches with relative location priors in a two stage classification process [START_REF] Gould | Multi-class segmentation with relative location prior[END_REF]. Malisiewicz and Efros have also shown that using image segmentation was efficient to improve the spatial support for object detection and recognition [START_REF] Malisiewicz | Improving spatial support for objects via multiple segmentations[END_REF].

In 1976, Rosenfeld et al. have formulated a process to reduce the ambiguities in object identification based on the relationships between the objects [START_REF] Rosenfeld | Scene labeling by relaxation operations[END_REF]. They proposed an ambiguity-reduction process by iterated parallel relaxation operations known as Relaxation Labelling. This approach was widely studied by the communauty in the context of graph matching for object recognition in videos [START_REF] Chevalier | Retrieval of objects in video by similarity based on graph matching[END_REF]. We show that relaxation labelling improves the global coherence of the segment classification and provides cleaner, regularized object extraction. Our framework for object detection and categorization is depicted in figure 1. Each row going from image segmentation to relaxation labelling describes the different steps to achieve semantic object extraction using a single segmentation method. The image is first segmented, feature descriptors are extracted on the segments and the classification of the segment into one of the semantic categories is performed based on these descriptors. The initial classification is further refined with the relaxation labelling algorithm. As the figure shows, it is possible to run the framework using multiple segmentation algorithms as the initial preprocessing step. When multiple segmentations and detection are available, it is possible to combine them using a late fusion schema, which is depicted by the red arrows going from the several segment classification boxes to the late fusion box. Again, it is possible to apply the relaxation labelling at the very end on the combined results as a last regularization step.

In this paper, we provide a detailed contribution for each step of the framework. In order to gain insights about the impact of image segmentation on the segment recognition performances, we applied our framework using four segmentation algorithms which will be introduced in section 2. In section 3, we introduce an efficient low level feature representation of the image segments. We propose to model the segments using color, texture and keypoint-based descriptors. For the latter, we propose a new way of sampling the keypoints locations to obtain a robust keypoint-based description of the segments. In the same section, we discuss the segment classification method focusing on how to obtain a multi-class probability estimates for each segment using Support Vector Machines (SVM) classifiers. Then, we present our methods for improving the recognition results: the relaxation labelling algorithm is described in section 4, while the late fusion strategies are introduced in section 5.

In section 6 we perform the quantitative evaluation of our approach and compare it with the current state-of-the-art. The experiments are carried using the MSRC-21 class database, a collection of 591 pictures of 21 object categories taken under different viewpoint and illumination conditions. Each image has a corresponding pixel-wise segmentation ground truth enabling training and evaluation (see figure 2).

Image segmentation

There exists a tremendous quantity of image segmentation approaches [START_REF] Freixenet | Yet another survey on image segmentation: Region and boundary information integration[END_REF][START_REF] Pal | A review on image segmentation[END_REF]. Our goal in this paper is not to propose a new segmentation algorithm, but to study the influence of the segmentation as a preprocessing step in the object detection and recognition pipeline. Hence, we apply our framework using four segmentation algorithms, each of them providing segmentations of different granularity (i.e. in terms of the number of segments produced) and accuracy (i.e. segments boundaries located at the actual object boundaries).

The first segmentation is a simple partitioning of the image into regular square patches of size 20 × 20 pixels. The size of the patches was chosen following the approach of Verbeek and Triggs [START_REF] Verbeek | Region classification with markov field aspect models[END_REF]. This produce an average of 178 segments per image using the MSRC dataset, and the segmentation accuracy is low. An example is given in figure 3(a). In the following we will refer to this segmentation as the grid segmentation, or gridseg.

The second segmentation algorithm is the dual contour/region segmentation of Prasad and Skourikine [23](figure 3(b)). The approach consists in an edge detection step followed by a Constrained Delaunay Triangulation (CDT) to close the region contours. The CDT ensures that the segments should not cross the actual objects boundaries, assuming that the edge detection is accurate. However, false edges are likely to appear in highly textured areas hence producing a high number of small triangular segments. On the other hand, low contrast edges can be missed and some segments can overlap between different objects (as shown in figure 3(b) below the wing of the airplane). The average number of segments produced by this method is 52, and the segmentation accuracy is slightly better than the grid. We will refer to this segmentation as the triangle segmentation.

The third segmentation was obtained using the synergistic segmentation of Christoudias et al. [7] (figure 3(c)). The algorithm is an improvement of the mean-shift color segmentation [START_REF] Comanicu | Mean shift: A robust approach toward feature space analysis[END_REF] with the addition of an edge confidence parameter [START_REF] Meer | Edge detection with embedded confidence[END_REF] in the feature space. The introduction of the edge confidence makes the segmentation more robust for low contrast region boundaries than the traditional mean-shift segmentation. We used the EDISON software package 1 with the default parameters value, and obtained an average of 45 highly accurate segments. We will refer to this segmentation as the edison segmentation.

The last segmentation algorithm is the one proposed by Felzenszwalb and Huttenlocher [START_REF] Felzenszwalb | Efficient graph-based image segmentation[END_REF] (figure 3(d)). It is based on the detection of boundaries between regions using a graphbased representation of the image. This algorithm is fast and has the ability to preserve detail in low variability regions while ignoring details in high variability regions. Again, we kept the default parameters value for segmentation and obtained an average of 21 segments per image. Since the number of segments is much lower than with the other algorithm, it is likely that some segments overlap different objects. However, the accuracy of the segmentation is usually good. We will refer to this segmentation as the graph-based segmentation or graphseg.

Region Classification

Description Space

The description space has to be rich enough to enable the computation of models for the recognition of image segments. We have based our description space on the combination of colour, texture and keypoint-based representation of the segment content. The shape of the segments is not considered as it is not robust with respect to the segmentation process, in the case of partial occlusions or in the case of complex objects made of different parts, and is also irrelevant for some object classes (e.g. sky, grass, water). We based the computation of the feature vectors of segments on the bag of visual words approach that was popularized by Sivic and Zisserman [START_REF] Sivic | Video google: a text retrieval approach to object matching in videos[END_REF]: for each descriptor, we compute a codebook (or dictionary) of representative elements using k-means++ [START_REF] Arthur | k-means++: The advantages of careful seeding[END_REF] clustering. Then, the descriptors computed on the image segment are matched with their closest representative in the codebook. The segment feature vector is the statistical distribution of the segment descriptors according to the codebook.

The content of a segment is described by a color feature vector x c = {x c1 , x c2 , . . . , x c|C| } where |C| is the dimensionality of the color codebook and x ci is the statistical frequency of the i th codework computed on the pixels belonging to the segment. We fixed the size of the color codebook to |C| = 100 representative colors computed on the training images in the HSV color space.

We compute a texture feature vector x t = {x t1 , x t2 , . . . , x t|T| } following the statistical approach to material classification using image patch exemplars by Varma and Zisserman [START_REF] Varma | A statistical approach to material classification using image patch examplars[END_REF]. The texture at a pixel is considered as a vector of grey levels of a 3x3 neighborhood centered on this pixel. We extract the texture around each pixel belonging to the segment, and match them to a texture codebook of size |T| = 100, computed on the training images.

Finally, we compute a keypoint-based feature vector x k = {x k1 , x k2 , . . . , x k|K| }. The keypoint based representation of image content is now undoubtedly one of the most effective approaches for the detection of semantic concepts [START_REF] Jiang | Representations of keypoint-based semantic concept detection: A comprehensive study[END_REF]. The keypoint-based representation relies on two steps, the localization of interest point and the computation of a feature descriptor located at these interest points. In our case, relying on the location of interest points introduces the potential drawback that some segments might not yield enough interest points for a statistically robust description, not to say might not yield any interest point at all. However, Nowak et al. [START_REF] Nowak | Sampling strategies for bag-of-features image classification[END_REF] have shown that random sampling of interest points gives equal or better classifiers than sophisticated multiscale interest point detectors for a moderate to large number of samples. Rather than random sampling the interest points, we sample them on the segments boundaries, which provides a good combination of the advantages of random and interest-point based sampling. Indeed, the salient point in images are most likely to occur on strong edges or corners, which correspond the objects boundaries extracted with an accurate segmentation. At the same time, it is possible to compute much more feature descriptors on the segment boundaries to obtain a dense, statistically more robust description of the segment. We have used the SURF feature descriptors of Bay et al. [4] for their low computational burden yet efficient discriminative power. Again, the size of the codebook of SURF descriptors was fixed to |K| = 100, and the dictionnary was computed by clustering the SURF descriptors extracted on the training set images.

The overall feature vector for a segment that will be used to train the models is the concatenation of color, texture and keypoint-based feature vectors x = {x c ∨ x t ∨ x k }. This is the simplest cases of early fusion of features.

Segments Classification

SVM have known an increasing popularity during the last 15 years since their introduction by Vapnik [30], due to their solid theoretical background, good practical results and their ability to deal with high dimensional data. To train an SVM model it is necessary to provide a representative set of training samples. We are working here on the problem of multi-class classification. Let us denote the training set S = {(x k ,Λ )|k = [1, . . . , K]}, with x k ∈ R n the feature vectors and Λ ∈ {λ 1 , . . . , λ M } the sample class. Given a set of training images we compute the training set S by assigning a label to every segments yielded by the segmentation algorithm. A segment is assigned label λ if more than 80% of its area is covered by pixels belonging to the class λ according to the ground truth segmentation. If no class reach this threshold, the segment is assigned to the class void.

We aim to get a probability estimate of the segment labelling given the whole set of possible classes. SVM have been initially formulated as binary discriminative classifiers with decision function f (x) such that sign f (x) is used to predict the label of any test example x. Platt [22] formulated an approximation of the posterior class probability p(y = λ l |y = λ l orλ m , x) by a fitting a sigmoid function (equation 1):

p(y = λ l |y = λ l or λ m , x) ≈ 1 1 + exp A f +B (1)
A and B are estimated by minimizing the negative log-likelihood function from the known training data and their decision values.

A binary SVM model is trained with each pair of classes. Given the binary probability estimates r i j = p(y = i|y = i or j), Wu et al. formulate the multi-class probability estimates as the optimisation of equation 2 [START_REF] Wu | Probability estimates for multi-class classification by pairwise coupling[END_REF]:

min p 1 2 M ∑ m=1 ∑ l:l =m (r lm p m -r ml p l ) 2 (2) subject to M ∑ m=1 p m = 1, p m ≥ 0, ∀m (3)
Hence, for each segment characterised by its feature vector x, we obtain from the SVM model a multi-class probability estimate vector p = {p λ 1 , . . . , p λ M }, ∑ M m=1 p λ m = 1 where

pλ i = p(y = λ i |x).
The whole process of binary SVM classification, binary probability estimates and multiclass probability estimates is implemented in the software package LibSVM [5].

Relaxation Labelling

The class probabilities p λ estimated with SVMs are inferred using only local features characterizing the segment content. Each segment is classified independently. We now want to increase the coherence of the global image labelling taking into account the relationships between the segments. Let us denote p i (λ ) the probability that segment i takes the label λ . Given the initial probabilities guess p (0) i (λ ), we can iteratively update the class probabilities of the segments using the relaxation labelling equations of Rosenfeld et al. [START_REF] Rosenfeld | Scene labeling by relaxation operations[END_REF] :

p (k+1) i (λ ) = p (k) i (λ )[1 + q (k) i (λ )] ∑ λ p (k) i (λ )[1 + q (k) i (λ )] (4) q (k) i (λ ) = ∑ j d i j ∑ λ η i j (λ , λ )p (k) j (λ ) (5)
η i j (λ , λ ) is called the affinity coefficient between labels λ and λ , d i j are coefficients satisfying ∑ j d i j = 1, ∀i. The j denotes the set of segments interacting with segment i. We considered it as the set the direct neighbors of the segment. d i j weights the contribution of the interactions between segments i and j. We set d i j = ρ(i, j)/ρ(i) with ρ(i, j) the length of the common boundary between segments i and j and ρ(i) the total length of the boundary of segment i, so that segments sharing a large portion of boundary have a stronger influence on each other than segments sharing a small boundary. Note that d i j = d ji .

Rosenfeld suggests to compute the affinity coefficient η i j (λ , λ ) as the correlation coefficient between the events that segment i has label λ and segment j has label λ [START_REF] Rosenfeld | Scene labeling by relaxation operations[END_REF] (equation 6, 7).

cor(λ , λ ) = cov(λ , λ ) (p(λ ) -p 2 (λ ))(p(λ ) -p 2 (λ )) (6) cov(λ , λ ) = p(λ , λ ) -p(λ )p(λ ) (7)
Hence q

(k) i (λ )
gives the way we want to change the labelling probabilities p (k) i (λ ), increasing highly correlated pairs of labels and decreasing uncorrelated ones. We can easily estimate the covariances from the segmented training database, as depicted in equation 8.

p(λ ) = |R λ | |R| , p(λ , λ ) = |R λ ,λ | |R| (8)
with |R λ | the number of segments labeled λ , |R| the total number of segments, |R λ ,λ | the number of pairs of adjacent segments having respective labels λ and λ and |R| the total number of pair of adjacent segments.

Late fusion of classifiers for segment labelling

In section 3, we saw how to obtain probability estimates of classes for each segment based on their local appearances. In section 2, we have introduced different segmentation algorithms for which the detection and recognition performances are evaluated in section 6. Hence, multiple segmentations with classified segments are available for the same image. A natural and seducing idea is to perform a late fusion of the classification results. Our fusion strategy is straightforward: first, we compute a new image segmentation mask from the the previously computed segmentations. This new segmentation is a partition of the image such that each segment S i in this new segmentation is an intersection of the previous segments.

An example of such a segmentation is shown in figure 4, where the segmentations of figure 3 are merged.

The segmentation hence obtained is more detailed than any of the previous ones, each segment having a one-to-many relationship with the original segments. Then, we assign the multi-class probabilities to the new segments. To do so, we combine the probabilities estimates obtained by the single segmentation detections using the max (equation 9), mean (equation 10) or multiplication (equation 11) operators.

p λ m = 1 Z max s∈S p s λ m with p s λ m the probability obtained using segmentation s. ( 9
)
p λ m = 1 Z ∑ s∈S p s λ m /|S|
p λ m = 1 Z ∏ s∈S p s λ m (11)
with Z a normalization factor to ensure that the probabilities sum to 1:

Z = ∑ M m=0 p λ m

Experiments

The goal of this section is to assess the impact of the following parameters in the quality of the object detection and categorization:

-The influence of the quality of the segmentation algorithm -The benefits of the neighborhood regularization method relaxation labelling -The interest of late fusion of multiple classification outputs using different segmentation support

The experiments were conducted on the MSRC-21 class image database. We split the database in two halves for training and testing. Following the protocol of the other works [START_REF] Shotton | Textonboost for image understanding: Multi-class object recognition and segmentation by jointly modeling texture, layout and context[END_REF][START_REF] Verbeek | Region classification with markov field aspect models[END_REF][START_REF] Gould | Multi-class segmentation with relative location prior[END_REF]36], we ignored the void class during training and evaluation, and horse and mountain classes were also ignored due to insuffiencient amount of representative in the database. The reported results are the pixel-wise accuracy, that is the percentage of pixels correctly classified with respect to the total number of pixels in the segmentation ground truth.

Impact of the segmentation algorithm

Figure 5 shows the overall pixel-wise accuracy obtained using the different segmentation algorithms presented in section 2. The best results are achieved using Edison, which clearly indicates the benefits of an accurate segmentation for the recognition. This is emphasized by the fact that the results obtained by the triangle segmentation, despite the approximate same number of segments per image, are much lower. Graphseg and grid segmentation lead to the same overall pixel-wise accuracy, despite their very different spatial support (large accurate segments versus small, arbitrary patches). It seems that the very limited view of the objects provided by the small square patches is still sufficient for recognition. It is interesting to see the differences of results at the object class level, as shown in figure 6. We can see that no segmentation yields better results for all the classes, but significant differences among the classes appears. For example, we obtain much worse classification results for categories dog and sheep using the graph-based segmentation than using the other algorithms, while the best results are obtained with this segmentation for the categories sky, building and cars. It is hard to tell from these results if one algorithm is particularly suited for some kind of object classes. However, an interesting result to note is the fact that good performances are obtained for some categories (body cow and sheep) with the grid segmentation while we would have expected that accurate segmentation would help for their recognition. The results obtained with the graph-based segmentation seems to suffer a lack of robustness in the recognition, since for some classes the results are very low compared with the other segmentation. The difference in recognition among the classes is due to the fact that the easiest classes are the From these results, we can draw the conclusion that each segmentation carry its own advantages that help to recognize some of the particular classes. The fact that the best results are achieved by edison contributes to the idea that an accurate segmentation improves the recognition, as was highlighted by other authors [START_REF] Gould | Multi-class segmentation with relative location prior[END_REF][START_REF] Hoiem | Geometric context from a single image[END_REF][START_REF] Malisiewicz | Improving spatial support for objects via multiple segmentations[END_REF]], Yet very different segmentation such as the high over-segmentation given by the grid and the coarser but accurate graphbased segmentation lead to the same recognition accuracy (overall). Nevertheless, in the case of single segmentation recognition, an over-segmentation should be favored since it appears to be more robust for the recognition of the different classes, despite the partial view of an object provided by the segments.

Impact of the relaxation labelling

Figure 7 presents the results obtained before and after relaxation labelling. The relaxation labelling step significantly increases the classification performances: 67.4 to 74.3 for triangle segmentation, 67.9 to 74.8 for grid segmentation, 68.7 to 75.1 for edison segmentation. Hence, we see that the regularization of the global labelling taking into account the relationships between neighboring regions is an efficient way of further improvement of the classification results. The probabilities estimates from the SVM model are sufficiently accurate to enable a convergence of the algorithm toward improved results. This is not the case, however, for the results obtained with graphseg, which are actually decreased after relaxation (66.9 to 66.8). Figure 8 presents the detailed classification results for the object classes before and after relaxation labelling. We note that, in fact, relaxation labelling is improving the results for most of the object classes over the direct classification results. However, for some classes which are the most frequent in the database (grass, sky), the results are decreased. Again, the large segments provided by the graph-based segmentation algorithm are a drawback for the relaxation labelling, since a wrong correction of a segment label has a stronger impact on the overall results.

Overall, the best classification performances are obtained using edison segmentation, followed by the grid, triangle and graphseg. The fact that the performances obtained with the grid are just slightly below the ones obtained by edison have to be contrasted. With a much lower number of segments per image, the processing time using edison segmentation is decreased both for SVM classification and for relaxation labelling.

Impact of the late fusion of multiple partitions

Figure 9 shows the classification accuracies obtained with the different merging strategies. The results obtained by any of the merging strategies outperformed the classification performances obtained using a single segmentation. The best results are achieved by multiplying the probabilities (73.2), then by taking the average probabilities (73) and taking the max (71.5). The multiplication operator strongly emphasize regions where each single detection agree on a common object class.

After merging the estimated probabilities, we are given for each new segment a multiclass probability estimate. We can then apply again the relaxation labelling, starting form these estimates.

Figure 10 shows the results obtained after relaxation labelling. Again, relaxation labelling improves the global coherency of the segments classification and has a positive impact on the overall classification results, even if the increase is not as significant as with the noisy, single segmentation detection results. It is interesting to see that the multiplied probabilities, which led to the best initialization did not lead to the best overall results after the relaxation labelling step. Multiplying the probabilities leads to an estimate with some regions already having very strong (e.g. not ambiguous) probabilities for some regions, which causes the relaxation to converge very fast without many changes. The max and mean operator allow more freedom for the convergence of the labelling, which in the end leads to better classification results. Overall, the best performances are obtained by the combination of the classifiers using the mean operator, followed by relaxation labelling which achieves 76.1 classification accuracy. This is a 1 point improvement over the best single segmentation detection results, 75.1 obtained with edison segmentation and relaxation.

Figure 11 shows the comparative results of our method with current state-of-the-art on the same dataset. Note that the results were not obtained using the same training and test datasets. Gould et al. [START_REF] Gould | Multi-class segmentation with relative location prior[END_REF] used 40% images for training, 60% for test, Shotton et al. [START_REF] Shotton | Textonboost for image understanding: Multi-class object recognition and segmentation by jointly modeling texture, layout and context[END_REF], Verbeek and Triggs [START_REF] Verbeek | Region classification with markov field aspect models[END_REF] split the dataset in two halves, Yang et al [36] reports the average results over a 5-fold cross validation. Our best method (merging multiple segmentation with mean operator) ranks second with for global pixel-wise accuracy with 76.1 behind Gould (76.5). The third one is our method using multiple segmentation and the max operator (75.4), then comes Yang et al. (75.1) and our method using edison segmentation (75.1).The main advantage of the method of Gould et al. is the introduction of the relative location priors between the object classes (a full 3-D spatial relationships between objects is inferred), which clearly helps the recognition as was also highlighted by Galleguillos et al. [START_REF] Galleguillos | Object categorization using co-occurrence, location and appearance[END_REF]. We model only the co-occurences between adjacent regions in the relaxation labelling. It will be interesting to model finer grain spatial relationships in the relaxation labelling, e.g. using different affinity coefficients for adjacent regions according to their spatial relationships such as above/below. The fact that the top 2 methods in the current state-of-the-art and ours rely on accurate image over-segmentation (superpixels for Gould et al. , mean shift patches for Yang et al. and our method) is again a plea for such kind of preprocessing. In figure ??, we show the category-based results of our best method compared with the state-of-the-art. Example images are shown in figure 13 using single segmentation approach and in figure 14 using the late fusion results.

Conclusion and perspectives

We have shown in this paper that the task of object detection and categorization can be successfully handled by the classification of the different image parts obtained by an initial image segmentation. Although trained using purely appearance based descriptors, the classification of segments already yields significantly good results. The combination of color, texture and keypoint-based descriptors is a powerful discriminative feature for the recognition of various object classes. In this work, we have kept the size of the codebook for the different descriptors low. However, there are evidences that a bigger codebook, at least for the keypoint-based descriptors, increases the classification results [START_REF] Jiang | Representations of keypoint-based semantic concept detection: A comprehensive study[END_REF]. Our experiments have confirmed our assumptions that an accurate segmentation method as preprocessing step has a very positive impact on the semantic object extraction results, while saving some computational burden. As far as the detail of the initial segmentation is concerned, we have shown that in a single segmentation/recognition process, an accurate over-segmentation should be preferred.

The relaxation labelling algorithm of Rosenfeld et al. [START_REF] Rosenfeld | Scene labeling by relaxation operations[END_REF] improves greatly the coherence of the global image labelling, by resolving ambiguities of local adjacent segments. The results obtained show an improvement over the direct recognition method for almost all the cases, and reach the current state-of-the-art obtained with more sophisticated method such as CRFs. The fact that this method is not optimal let the way open for future research on more global optimization that could improve the results even further.

Finally, we have proposed a new late fusion schema of the results of classifiers trained on the same initial feature space but using different segmentation algorithms as preprocessing. This is the first adaptation of late fusion approach in the image segmentation framework to our knowledge, and the results are promising. A direction of future research will be to apply our framework for object detection by combining several layers of coarse to fine segmentation methods, in order to capture and propagate recognition results over the different scales.

Fig. 1

 1 Fig. 1 Object detection and categorization framework.

Fig. 2

 2 Fig. 2 MSRC-21 class database, images with their corresponding pixel-wise labelling (best viewed in color).

  Fig. 3 Examples of the different segmentation methods (best viewed in color).

Fig. 4

 4 Fig.4Example of the fusion of the segmentations shown in figure3. Very small regions (less than 50 pixels) are fused their biggest adjacent regions to avoid unnecessary isolated pixels.

Fig. 5

 5 Fig. 5 Pixel-wise accuracy for the direct SVM segment classification obtained with the different segmentation algorithms.

Fig. 6

 6 Fig. 6 Pixel-wise classification accuracy of direct segment classification using various segmentation algorithms (best viewed in color).

Fig. 7

 7 Fig. 7 Global pixel-wise classification accuracy of runs before and after relaxation labelling. Name SVM are the results of direct segment classification, Name RLB are the results obtained after the relaxation labelling.

Fig. 8

 8 Fig. 8 Results of applying relaxation labelling to the segment classification obtained by graphseg on the different object classes.

Fig. 9

 9 Fig. 9 Comparison of the classification accuracies obtained by the single segmentation detection results and by the combined segmentation with the different operators.

Fig. 10

 10 Fig. 10 Classification performances after the relaxation labelling step using the combined segmentation results as initialization.

Fig. 11

 11 Fig.11Comparison with current state-of-the-art. Dark blue are results reported in the litterature, light green our results with late fusion, light blue our results with single segmentation approach.

Fig. 12

 12 Fig.12Comparison with current state-of-the-art. Dark blue are results reported in the litterature, light green our results with late fusion, light blue our results with single segmentation approach.

http://www.caip.rutgers.edu/riul/research/code/EDISON/index.html


Antoine Seilles
email: antoine.seilles@lirmm.fr

Jean Sallantin
email: jean.sallantin@lirmm.fr

Nancy Rodriguez
email: nancy.rodriguez@lirmm.fr

Stakeholder Detection for Online Debates

Keywords: H.5.3 [Group and Organization Interfaces]: Organizational design, Web-based interaction Experimentation E-democracy, E-communities, Stakeholder detection, Community detection, Opinion, Annotation, Role, Relation

This paper presents a work in progress about stakeholder detection for online debates. We propose an approach based on classical community detection methods applied to semantic social networks representation. We defend that new web2.0 tools should assist users to define semantic relations between users, groups and roles based on social interaction analysis. The main goal is to provide new mecanisms for moderation decreasing misunderstandings and highlighting unexpected behaviors.

1.INTRODUCTION

The web offers new hopes for e-democracy, providing many new ways of interacting between citizens and civil servants. One of the key feature of democracy is the possibility to debate. Websites for online debates use classical web2.0 tools for enabling discussions: forums, blogs, instant messenger, etc. However, these tools have not been designed for debates and have scalability limitations. We argue that two major aspects have to be taken into account for online debates: the possibility to express opinions and stakeholders. Within a large scale debate, one needs to know the main tendencies: what are the alternatives options and which group supports the various options. Our approach is to use semantic web technologies to represent users interactions and build new methods of communities and tendencies detection. This paper starts with a reminder of the principal hopes provided by e-democracy and the currents limitations of online debates. Then, we present an alternative solution to classical opinion mining approaches. Our solution is based on semi-structured annotations. We present a model to unravel a web user's identity and we present how this model matches with existing RDF ontologies. Then, we present Stakeholder detection as a particular case of community detection. We discuss the notion of relationship and classical graph-based representations for social networks. Finally, we present our experimental approach to support stakeholder detection and organization.

2.E-DEMOCRACY AND ONLINE DEBATES

The main goals of e-democracy are to facilitate open exchanges of controversial political ideas, to increase citizens participation and to reduce organizational costs of consultation [START_REF] Price | Citizen Deliberating Online : Theory and some Evidence[END_REF] [25] [START_REF] Desquinabo | Stakeholder e-Participation in Local Planning: The Camargue Park Case[END_REF]. Web tools for e-democracy facilitate the expression of opinions due to anonymity and due to accessibility from everywhere at anytime. This ease of access is also a factor to decrease organizational costs. Nowadays, most of the web tools used for e-democracy are discussion tools (such as blogs or forums) dedicated to e-consultation. These tools have a cost of moderation and animation [START_REF] Confino | Blogs territoriaux, réseaux sociaux et nouveaux enjeux du web2.0 pour les collectivités[END_REF]. A reason for this moderation and animation cost is the lack of an executive summary. Web applications that provide debate summaries need to process data to extract opinions and categorize the statements. They are not linked to discussion tools. There is no available tool to structure an argumentation (the best feature currently is the possibility to type a statement as pro or con using modalities such as "I like" or "I agree/disagree"). This lack of structure and summary leads to huge costs in data processing of large scale debates.

Another point to highlight is that democracy is not only made of debates. Debate in democracy is only one step of a collaborative process to decide [START_REF] Vedel | L'idée de démocratie électronique : origines, visions, questions[END_REF]. A dedicated tool for democratic discussions should be inter-operable with other tools (online or not), like calendars, pole applications, social network application, etc.

We have adopted the web semantic technology of RDF (Resource Description Framework) to represent debates data (opinions and argumentative structures) and to facilitate interoperability. RDF allows to represent relations between subject and object and is a standard for data exchanges. [START_REF] Chabrol | Préalable à une classification des actes de parole[END_REF] defines an opinion as a discursive act in which the speaker "models" explicitly or implicitly the object of his statement with the dimensions "possible/impossible", "desirable/undesirable", "beautiful/ugly", "pleasant/unpleasant", etc. Opinion mining is one application of the natural language processing domain. The main assumption in [START_REF] Harb | Web opinion mining: how to extract opinions from blogs?[END_REF] is that an opinion can be detected by the adjectives used. Two kind of methods exist to detect opinions: using a corpus of opinions done by experts [START_REF] Plantié | Is a Voting Approach Accurate for Opinion Mining?[END_REF] or using adjectives repositories such as WordNet [START_REF] Miller | WordNet: a lexical database for English[END_REF] [START_REF] Liu | Tutorial on sentiment analysis[END_REF]. Results will largely differ depending on the corpus used. One adjective may express a different opinion depending on the context [START_REF] Wilson | Recognizing contextual polarity: An exploration of features for phraselevel sentiment analysis[END_REF]. All these methods are not dynamic and context related. We suggest to use semi-structured annotations as a dynamic alternative to opinion mining. [START_REF] Veronis | Annotation automatique de corpus : panorama et état de la technique[END_REF] defines annotations as any new information added to raw data. [START_REF] Lortal | Médiatiser l'annotation pour une herméneutique numérique : AnT&CoW[END_REF] splits annotations in two categories: semantic annotations are meta-data added to a document, discursive annotations are comments attached to a document and linked together by a discursive structure. Both annotations can be associated to a full document or only to a part of a document.

3.ANNOTATION EXPRESSING OPINIONS 3.1Limitation in opinion mining

3.2Semi-structured annotation

Semantic annotations are the kind of meta-data RDF can express. Most of the time, these semantic annotations are produced by professionals specialized in knowledge representation. A discursive annotation is similar to a forum post except that the discussion can be represented by a graph instead of a thread (posts can have multiple replies and are ordered by reply status). One interesting feature of discursive annotations is the possibility to highlight the part of a post to which a comment replies. This feature is badly implemented in most of the current forums by the "quote" functionality. This property allows users to highlight the core statements.

[20] offers solutions for users to produce meta-data while they enter a post in a forum or an article in a wiki. Using the same methodology, we present a solution for producing both semantic and discursive annotations. Figure 1 shows one of our annotation forms. It contains a choice of "emoticons" to express a mood, a choice of labels to express an opinion and text-areas to add comments. Once validated, these comments are stored using RDF vocabularies: SIOC, DublinCore, RSS1.0, and Annotea annotation Schema. Currently, these vocabularies don't allow to represent the core information to enhance social network analysis: opinions, moods and comments status. [START_REF] Chesñevar | Towards an argument interchange format[END_REF] offers an ontology to express comments status. The AIF ontology allows to represent argument networks. The NiceTag ontology [START_REF] Monnin | Speech acts meets tagging : NiceTag ontology[END_REF] is designed to represent the action of tagging. It's possible to represent the fact that a tag expresses an opinion. Figure 2 shows a limited representation of an annotation. We have not yet included ontologies such as AIF or NiceTag. 4.DIGITAL IDENTITY REPRESENTATION [START_REF] Georges | Représentation de soi et identité numérique[END_REF] presents a model to unravel users' identity. The digital identity is a representation of the user's declared profile, activity and statistics. The first component of digital identity is the declarative identity constituted of every data the user give to the system about himself. Typically, when a user subscribes to a new application he is invited to fill a form containing personal details (address, age, gender, interests, friends, etc.). Declarative identity data can be represented by the FOAF ontology. The FOAF ontology is dedicated to represent personal data and relationships. The second component of digital identity is the acting identity constituted of all interactions the user has through the system. For example, when he modifies his status or when he sends a message. The SIOC ontology offers a partial representation of the acting identity. The last component of digital identity is the calculated identity. It is constituted of numbers calculated by the system and concerning the user (for example, statistics on his browsing or chatting activities).

Results of classical Social Network Analysis methods are parts of the computed identity. The ontology SemSNA [START_REF] Ereteo | Semantic Social Network Analysis[END_REF] is dedicated to represent results of such methods. Figure 3 summarizes a matching between digital identity and ontologies.

Figure 3. Ontologies to Represent Digital Identity

We will defend in the next part of this paper that, by using results of SNA methods applied to the acting identity data, it becomes possible to compute and offer a structured representation of social networks. By structured representation of social networks, we mean a social network where individuals are represented "linked together" by labeled relationships. They also are associated to the roles they play in the network (leader, troll, etc.). In other words, we say that it's possible to deduce a FOAF representation of someone's social network using SNA methods applied to a SIOC representation.

5.STAKEHOLDER MANAGEMENT 5.1Stakeholder detection

Stakeholders are people sharing interests and opinions. Most of the time, stakeholder groups are already organized and act as lobbying groups during debates. We are interested in detection of unorganized and unidentified stakeholder groups. According to [START_REF] Callon | Qu'en pensent les citoyens ?[END_REF], these groups deserve more attention than already existing stakeholder groups. They stress new doubts about issues of the debate and are weaker than existing groups. The dynamic of a debate is correlated to the dynamic of stakeholder groups. A new doubt creates new subjects of debate and knowledge emerges of each debate. New knowledge creates new doubts. But stakeholder detection is not only a simple community detection problem. Community detection is based on representing social networks by mono-relational graphs.

Stakeholder detection is based on expressing opinions. We share the same conclusion as [START_REF] Ereteo | A State of the Art on Social Network Analysis and its Applications on a Semantic Web, SDoW[END_REF], social network analysis need a social network representation concerned with semantics not only with syntax as it is the case in classical graph-based representations.

5.2Community detection

In the community detection domain, the definition of a community is only linked to sociometry and graph theory and not to a true social theory. [START_REF] Fortunato | Community detection in graphs[END_REF] presents a review of community detection methods and defines communities as being "clusters or modules, groups of vertices which probably share common properties and/or play similar roles within the graph". In such methods, only the amount of relations and of nodes in the graph is concerned. The roles of individuals, the different natures and intensities of relationships are not taken into account. Indeed, they are presented as an explanation and supposed unknown.

Community detection lays on mathematical properties of specific graphs patterns [START_REF] Scott | Social Network Analysis : A Handbook[END_REF]: components (isolated connected subgraphs), cycles (paths where starting and ending vertices are the same) and cliques (each vertice is linked to all others). Referring to Granovetter's theory of strength of weak ties [START_REF] Granovetter | The Strength of Weak Ties[END_REF], such methods can successfully detect groups of individuals strongly tied each others and similar. Granovetter in [START_REF] Granovetter | The Strength of Weak Ties : A Network Theory Revisited[END_REF] revisits its own theory through a review of empirical studies. Most of his assumptions seem to be validated, but depending on the context, the interpretations of the assumptions differ. [START_REF] Granovetter | The Strength of Weak Ties[END_REF] proposes that every relationship can be quantified measuring an intensity or a strength. The definition given for the strength of a tie is the following : "a combination of the amount of time, the emotional intensity, the intimacy (mutual confiding), and the reciprocal services which characterize the tie". A group is characterized by the fact that individuals are tied through strong ties. Two individuals strongly linked must share many common personal characteristics. This tends to define a group as a set of similar individuals and implies that a bridge between two groups might be a weak tie. Figure 4 summarizes the impact of strong and weak ties in community detection. Empirical studies [START_REF] Granovetter | The Strength of Weak Ties : A Network Theory Revisited[END_REF] show that the definition of the strength of ties depends on the context and the nature of the tie. Two persons with a strong tie for business are not necessary strong friends. Indeed, this idea may refer to the notion of Netdom developed by White [START_REF] White | Identity and Control[END_REF].

White defends that a network is composed of different subnetworks depending on domains. Two individuals may be differently linked depending on the domain (business, family, politic, etc.).

5.3Web interactions, Communities and Roles

The web provides many differents way to interact between users. These interactions are data for social networks analysis. Some platforms such as Facebook are dedicated to build social network. Another approach is to extract social network from existing interactions (email [START_REF] Tyler | Email as spectroscopy : automated discovery of community structure within organizations[END_REF], IRC [START_REF] Mutton | Inferring and Visualizing Social Networks on Internet Relay Chat[END_REF], etc.). Referring to the Nadel's theory of social structure [START_REF] Nadel | The Theory of Social Structure[END_REF], we adopt the strategy of extracting a social network from a set of interactions between users. Nadel defines a relationship as a set of social interactions between two individuals. Using tagging and annotation activity, it becomes possible to detect two users sharing the same interests and supporting a same claim. This approach is similar to recommendation systems based on personal activities [START_REF] Iskold | The Art, Science and Business of Recommendation Engines[END_REF].

Most of recommendation algorithms are based on similarity of profile or activities history. Referring to Granovetter's theory, classical community detection and recommendations approach based on similarity are effective and constitute the core of a stakeholder community. However, similarity doesn't provide a solution to organize a group. A complex organization is not made only of similar individuals. Most of the time, an organization is the coordination of complementary individuals. Furthermore, the lack of heterogeneity in a group due to similarity has a perverse effect : polarization and radicalization of opinions. This effect is one hypothesis of Granovetter's theory and is one of the effect feared by Price [START_REF] Price | Citizen Deliberating Online : Theory and some Evidence[END_REF] about online discussions. Therefore, we suggest to extract a social network not only on similarity but also on opposition and weak ties.

Nadel defends that a society is structured by roles over relationships. An individual playing a role is supposed being aware of the role he plays. A role defines a behavior through possessions and skills and through relationships between the individual playing the role and others. Because a relationship is defined by a set of interactions, an individual playing a role is supposed to act a specific way in each situation. Because the definition of a role is supposed to be known by everybody, an individual playing a role is exposed to social sanctions if he doesn't behave correctly.

We base our approach on representation and storing of rich social interactions. We can detect groups sharing a same opinion about a subject querying RDF representation. We can assist users to define their relationships and their roles revealing patterns of users behaviors. We try to create a recommendation system based on complementarity, not only on similarity. The next part of this paper presents an experimental approach and our expected results.

6.EXPERIMENTAL APPROACH

Our forthcoming experiment concerns users acceptability of roles and labeled relationships. Do users correctly use semistructured annotations? Do semi-structured annotations provide rich interactions we can exploit to analyse the network of users?

Two groups of users have to discuss a given subject using semistructured annotations. Each group is a set of individuals already knowing each other. Users of the first group are identified by first name and last name. Users of the second group are identified by anonymous pseudonyms. The system will log all the information concerning interaction between users: the use of a same tag, replies support or opposition, etc. After a determined duration, the system will give a summary of interactions between users and will ask them to identify relationships between them.

We expect the following results: Patterns should emerge demonstrating the existence of different relationships between users and the redundancy of these relationships. Patterns should emerge between users linked by the same type of relationships. It validates the existence of classes or categories of users which is a necessary condition for existence of roles. Users already know each other and already have interactions and relationships outside of the system. Therefore, users identified by last and first names should be easily aware of their relationships. The comparison between anonymous and non-anonymous users should stress that knowing each other identity has an impact on interactivity. Indeed, we expect that anonymous users will express more opinions.

7.CONCLUSION

We presented a context of development of new web 2.0 applications dedicated to online debates. We briefly discussed the need for web semantic representation. We discussed the need of new social network analysis based on labeled relationships. Applications offer more and more way to interact but offer poor vocabularies to define relationships between users. We suggest an approach based on Nadel's theory dedicated to organization of social networks. We argue that a structured social network, composed of individuals playing roles and linked by labeled relationships, represented by the FOAF ontology can be deduced using SNA methods applied to a representation of social activities or interactions such as the SIOC ontology.

8.ACKNOWLEDGMENTS

This research was sponsored by the Intermed-ANR project. Thanks to Martine Hornby for her technical support.

Figure 1 .

 1 Figure 1. An annotation form

Fig 4 .

 4 Fig 4. Strong and Weak ties in community detection