Nicolas Larrieu
email: nicolas.larrieu@enac.fr

How can model driven development

Keywords: Certification, integration, micro-and mini-UAS, networked swarms, security, UAS applications, UAS communications, UAS testbeds

approaches improve the certification process for UAS ?

Introduction

This paper deals with new Model Driven Development (MDD) approaches that are inherited from existing aerospace and aeronautical system developments and that could be useful for the certification of UAS (Unmanned Aerial System) design. The principle of MDD is to build the initial system with high level models and to take advantages of auto generation process to be able to produce software and byte codes of the final system directly from the high level modeling. This approach helps engineers not to be dependent of a specific development language (mainly C or ADA language in this field) and allows also verification, validation and certification of the final product at an early stage of the development life cycle. This paper investigates how a model driven design can improve UAS system robustness. Indeed, UAS are currently flying in specific and segregated airspaces, separated from regular aircraft. Thus, to be widely used in the future, UAS will need to be deployed in the same airspace as regular aircraft. Nevertheless, their unmanned and automated features make this goal very difficult to certify. This is why it is necessary to verify, validate and certify the different parts of the UAS (operating system, communication system or even payload depending on their application) in order to be compliant with the whole airspace certification process.

Thus, this paper wants to demonstrate how MDD approaches which are extensively used in aerospace and aeronautical fields at this time can improve the development of complex systems in the UAS field. To do so, a specific MDD methodology is introduced and instantiated in the context of the French project SUANET (Secure Uav Ad hoc NETwork) which aims at developing a secure communication ad hoc network for UAV swarms.

The outline of this paper is the following. In the next section, we introduce the two main documents DO 178 C and DO 331 which were released by RTCA 1 in 2012. They provide guidance on model driven approaches for design and certification of aeronautical systems. In section 3, we focus on a specific UAS issue: how to integrate UAV swarms into the traditional airspace? By starting with this issue, we explain how UAS systems could take advantage to consider aeronautical model driven approaches in their own design cycle. We highlight a specific French research project (SUANET: Secure Uav Ad hoc NETwork) whose objectives are to integrate a UAV swarm into the French civilian airspace and we outline how we can benefit from model driven approaches for such a task. In the fourth section, we present a specific case study considered in the SUANET project where we have started to apply aeronautical model driven approaches. We introduce the main advantages for this practical use case on two aspects: modularity and reusability.

Overview of model driven development approaches

Traditional software engineering has been using model driven development tools for a long time. Unified Modeling Language (UML) [START_REF] Booch | OMG Unified Modeling Language Specification[END_REF] is one of the most effective methodologies to conduct traditional software design. Nevertheless, when we consider more specific engineering fields such as aeronautical or aerospace system design this tool cannot be used "off the shelf". The main problem with traditional UML-based software design is the lack of certification considerations in the tool chain used to generate the final system software. It may not be a problem for classical applications such as Web services [START_REF] Miller | Designing Web Services Using UML[END_REF], tools for engineering [START_REF] Bahill | Using objected-oriented and UML tools for hardware design: A case study[END_REF], or game applications 2 ; but it represents a huge problem when you consider critical applications such as an aircraft or a satellite. In this context, it is necessary to take into account the certification of the final software, and to integrate the tool chain used for design in the standardization process followed in such a specific field.

Aeronautical software design

In this paper, we consider the certification process followed by the aeronautical industry when new embedded software has to be designed for a specific purpose. Several standards have to be met. We will focus on the two most closely related to our topic: DO 178 C [START_REF]Software considerations in airbone systems and equipment certification[END_REF] and DO 331 [START_REF] Do | Model-based development and verification supplement to DO-178C and DO-278A[END_REF].

DO 178 C: Software Considerations in Airborne Systems and Equipment Certification

In 2012, RTCA released the third version of the DO 178 document which gives guidance for airborne system certification. This new version takes into account the latest developments in terms of model driven approaches for software system design. The emphasis is placed on model driven approaches that are able to automatically generate software code by taking as inputs only high level models which represent the different features and behaviors of the final system. It introduces in particular the possibility to validate such a system by using formal methods in order to reduce the amount of testing for the validation of the final product. This is a major

DO 331: Model-Based Development and Verification

In addition to DO 178 C, another standardization document, DO 331, deals with tools and methods used to automatically generate software and to validate these high level models in line with initial system specifications. In this document, advanced verification methodologies are introduced. RTCA recommends the use of three different technologies to ease the verification process: model checking, formal proofs and code assertions [START_REF] Gigante | Formal Methods in Avionic Software Certification: The DO-178C Perspective[END_REF]. These three techniques have been used for a long time in different engineering fields and are mature enough to be introduced into complex environments such as aeronautical certification and validation processes.

Model driven approaches for UAS design

These new techniques to model and certify an aeronautical system can be integrated into the global process for UAS design. This integration will have two main advantages for engineering. Firstly, the UAS design step will be facilitated thanks to modularity and reusability of model driven design approaches. Secondly, the certification of the global UAS system will be able to take advantage from formal validation techniques dedicated to work with inputs such as high level models. In the next sections of this article, we highlight how a model driven approach first developed for aeronautical design purposes can be extended to the UAS field. We will outline the effectiveness of such an approach and we will illustrate it through a case study: the SUANET project.

Integration into the civilian airspace: a complex topic

In this section, we focus on a specific UAS issue: how to integrate UAS into the traditional airspace? UAS integration into the civilian airspace can be considered from different points of view (path planning [START_REF] Ravich | The integration of unmanned aerial vehicles into the national airspace[END_REF], communication compatibly 3 , certification, etc). We will focus solely on the certification issue in this article. It means that if a company wants to deploy a UAV swarm in the civilian airspace it needs to justify that its system is fully compliant with the certification process of any aircraft in the same civilian airspace.

Indeed, this task can be complex, given that an aircraft has a lot of certification documents to produce before being cleared to fly in the civilian airspace. Thus, if a traditional testing approach is followed for UAS certification it can result in a huge amount of testing being required. This is why model driven approaches have a lot to contribute for certification processes of UAS, by enabling designers to avoid some of the traditional testing steps by using, for instance, formal methods for validation.

Taking advantage of aeronautical model driven approaches

Different proposals have been made for the certification of complex aeronautical systems. UAS ought to take advantage of the numerous research projects that have been conducted in this area by both public and private companies.

Different specific issues have been considered in the literature. For instance, [START_REF] Jacobs | Model-Driven Development of Command and Control Capabilities For Joint and Coalition Warfare[END_REF] have introduced model-driven development to enhance command and control capabilities of an aircraft. [START_REF] Horváth | Model-driven development of ARINC 653 configuration tables[END_REF] have been conducting model-driven development for IMA (Integrated Modular Avionics). [START_REF] Dubois | The product line engineering approach in a model-driven process[END_REF] have considered the consequences of model-driven development for the whole product line process of an aircraft. However, these examples are always dedicated to one specific issue of the aircraft development. We can cite [11] which discusses a global model driven process for aerospace systems, but we cannot find in the literature a similar approach dedicated to the aeronautical field. This is why we would like to cite [START_REF] Varet | New methodology to develop certified safe and secure aeronautical software -an embedded router case study[END_REF] where we have introduced a new model driven methodology for fast prototyping of generic aeronautical systems. We have illustrated this methodology in the development of a new embedded router for future aeronautical communications [START_REF] Varet | Design and Development of an embedded aeronautical router with security capabilities[END_REF].

By taking advantage of previous research contributions in the aeronautical field which have already shown their capabilities, we believe it is possible to accelerate the UAS certification process. Thus, we have chosen, in the next sub section to describe a specific French project (SUANET: Secure UAV ad hoc network). Its objectives are to integrate a UAV swarm into the French civilian airspace by considering mature and advanced model driven design approaches.

SUANET project objectives

In this project, started in September 2013, and planned to last for 36 months, we are planning to study the possibility of transferring model driven technologies from traditional aeronautical areas to UAS. The objective is to increase the confidence we will have in the final UAS and to accelerate the certification process with the French Civil Aviation Administration (DGAC 4 ). In this project, ENAC (the French Civil Aviation University) has joined with a French company DELAIR TECH located in Toulouse. DELAIR TECH 5 is specialized in the design of UAVs with a dedicated payload. Each customer can choose a specific application to deploy inside the UAV. Different examples of UAV applications have already been developed such as surveillance, communication networks and aerial photography.

Given that different applications can be investigated with such a UAS; we chose to illustrate specifically how a swarm of UAVs can improve video surveillance of geographic areas affected by natural disasters (for instance fire, storm, typhoon, etc.). Thus, in the SUANET project, we will design a complete communication architecture for the whole UAV swarm and the ground station control. We will also investigate the interconnection with external networks such as the national security network. This connection with external networks and the requirement of communication between the different UAVs of the swarm imply that we will have to focus our research on new secure communication solutions. These solutions would need to be light enough to be integrated on a mini-UAV but robust enough to avoid any malicious behaviors from the environment.

Video surveillance application

Mini-UAV characteristics

The miniaturization feature of DELAIR TECH's UAVs (DT-18 UAV) is an important characteristic to take into account in the development of the final solution. Their small size must be taken into account when designing the system in terms of CPU, energy consumption or means of communication. In the next section, we will demonstrate how a model driven approach initially developed for aeronautical purposes can be instantiated for the UAS environment.

We will give specific examples on how it can be applied in the SUANET project. Modularity and reusability of the UAS will be highlighted and technical solutions to provide security and means of communication within a swarm of UAVs will be investigated.

Case study: transition of a model driven design from the aeronautic field to the UAS environment 4.1 Model driven methodology principles

The previous methodology we designed to develop generic systems for aeronautical purposes (see [START_REF] Varet | New methodology to develop certified safe and secure aeronautical software -an embedded router case study[END_REF] for details) is built on the following three steps: Step 1 has to be manually written, the most efficient approach is to produce a Software Requirement Specification (SRS) file detailing the different behaviors of the final application.

For step 2, we use Mathworks Simulink and Stateflow tools 7 to model the different partitions. Their graphical features help the designer to fast generate high level behaviors. An example of high level models is described in Figure 3. In this step, we can already work on the certification process because it is possible to use formal validation techniques directly on the high level models. This material can be also used by the development team as part of the final certification documents it needs to produce to the regulator (Federal Aviation Administration or European Aviation Safety Agency in our context). For instance, Stateflow is able to detect any dead state in the high level model which will correspond to a dead code in a traditional design approach. The main difference is in the rapidity which with we are able to detect this dead state: with a high level model tool it is automatically analyzed whereas in a traditional approach only the developer is able to detect it by manually reviewing the final code.

In step 3, we used GeneAuto [START_REF] Izerrouken | Design and Development of an embedded aeronautical, Certifying an Automated Code Generator Using Formal Tools: Preliminary Experiments in the GeneAuto Project[END_REF], an Open Source generator to generate the final C language software taking as input high level models and providing source codes in C language. This step can also improve the certification process given that, if your auto-generator is certified, you validate that the final source code is compliant with the features modeled at step 2, and then you do not need to manually realize extensive testing on the final source code. Please note that GeneAuto is certifiable but not certified at this time. However, several commercial tools exist in the industry to convert high level Simulink or Stateflow models to certified embedded code. However, they are all proprietary, expensive and with narrow freedom for the end users, this is why we did not select them in the SUANET project. After step 3, please note that there is still important work to do in order to generate a final binary compliant with the UAS hardware where you intent to deploy your system designed with this methodology. This part of the process is outside the scope of our UAS certification issue and will not be described in this article (details are provided in [START_REF] Varet | New methodology to develop certified safe and secure aeronautical software -an embedded router case study[END_REF] for the aeronautical field).

The next part of this section is dedicated to illustrating through a specific case study how model driven design can accelerate the development of new systems. For instance, we are going to reuse in the SUANET project some specific parts of a previous design (mainly communication and security features) and thus to take advantage of modularity and reusability of our model driven design approach for the specific field of UAS.

Modularity

In previous research, based on our model driven design approach, we produced a full compliant secure and safe router for aeronautical communications [START_REF] Varet | Design and Development of an embedded aeronautical router with security capabilities[END_REF]. This device is able to exchange different types of information between the ground and the aircraft (point-to-point communications) in one or several safe and secure communication tunnels. In the SUANET project, the communication paradigm is not point-to-point communications because each UAV which belongs to the swarm can be either one communication relay or an end-device (with surveillance capability in this case) as mentioned in Figure 1. The communication paradigm used to make the UAV swarm communicate is thus a Mobile Ad Hoc Network (MANET) [START_REF] Rajabhushanam | Survey of Wireless MANET Application in Battlefield Operations[END_REF] paradigm. Even if the routing function is different in the two paradigms, the aeronautical modular design detailed in Figure 4 will facilitate the final UAS system design. Indeed, specific models such as Piface (i.e. the level 2 network interface) will be derived to be compliant with the new layer technology (mainly IEEE 802.11 "WIFI" [16] in our video surveillance use case). For the Pfr partition dedicated to filtering, routing and QoS (Quality of Service), a new routing function will be designed to be compliant with the ad hoc feature of the network, but the whole framework of network layer will be maintained. Finally, the global design will be eased due to the global modularity of our model driven design approach. The certification process will also be accelerated given that different parts of the models have already been validated in our previous research.

Reusability

Model driven design approaches can also enhance software reusability. Indeed, a specific part of the new architecture designed for SUANET will be directly derived from the original aeronautical one: the Pse partition dedicated to enforce the security for the different data exchanged between senders and receivers. In section 3.2, we pointed out how security inside the UAV swarm and between the swarm and the additional networks (control and national security agents for instance) is an important issue. To do so, specific communication functions (such as authentication, integrity or confidentiality) have to be designed. The initial aeronautical Pse partition contains these different features and consequently, can be transfer directly from the original aeronautical design to this specific UAS system. For the same reason as in section 4.2, the certification process will be facilitated given that the different functions and modules of Pse partition have already been validated.

Conclusion and future work

In this paper, we have addressed the following question: "how can model driven development approaches improve the certification process for UAS?". As a first step, we introduced model driven development approaches that can be inherited from airspace and aeronautical systems and that could be reused in UAS design. As a second step, we demonstrated how a model driven design can improve UAS system robustness. To illustrate our thesis, a case study, derived from the SUANET research project, was introduced and focused on the main advantages for UAS environments: modularity and reusability.

The SUANET project has recently started (September 2013) and we still have several tasks to undertake:

1. Enhance design: even if model driven approaches enable reusability of previous design, there are sill some specific parts of the design that we need to produce, for instance the dedicated functions to implement MANET routing;

2. Development of the final UAS: there is a significant part of the development still to conduct. Indeed, the different partitions identified in section 4 will be implemented on real systems. SABRE Lite 8 is the final architecture identified in the project and some technical adjustments will be necessary to produce a final binary from the auto generated source files in C language;

3. UAS testbed: an exciting part of the SUANET project deals with testing the software solution we proposed in the real environment. We will be able to test our communication and security solutions for UAS with 3 different mini-UAVs from DELAIR TECH company. These tests are planned in the second half of 2014 and they will give a strong validation environment for our methodology and related technical solution.

In a more prospective research work, additional functionalities could be investigated for future UAV swarms. For instance, communications between two different groups of UAV swarms sharing the same mission but not the same goal. We can imagine reconfiguration features of the different groups in terms of number, functionality or positioning. These reconfiguration features require future communication and security components. We need to develop them to enhance the level of service of the final UAS we plan to propose.

2 Finally, section 5

 25 1 RTCA: Radio Technical Commission for Aeronautics P a p e r C e p t I n c concludes this article and presents the different future contributions we are planning during the next months of the SUANET project.

Figure 1

 1 Figure1describes this video surveillance scenario where different UAVs communicate with each other depending on their position in the area. For instance, DT2 acts as a communication relay if DT1 and DT3 cannot directly communicate. The different monitoring data is exchanged with the ground station which collects this data and can transfer some of it to the external network for collaborative purposes.

Figure 2 (

 2 Figure 2(a) illustrates the legacy communication antenna used between the ground control station and DT1 of our video surveillance scenario to remotely pilot the UAV swarm and receive the observed data.Figure 2(b) describes the HMI

Figure 2 (

 2 Figure 2(a) illustrates the legacy communication antenna used between the ground control station and DT1 of our video surveillance scenario to remotely pilot the UAV swarm and receive the observed data.Figure 2(b) describes the HMI

Figure 1 :Figure 2 :

 12 Figure 1: video surveillance use case in the SUANET project

Figure 3 :

 3 Figure 3: examples of high level models (step 2)

Figure 4 :

 4 Figure 4: examples of a modular design

Table 1

 1

	describes the main technical characteristics of
	DT-18 UAVs 6 .

Table 1 : DT-18 UAV characteristics Characteristic Value

 1

	Model	DT-18
	MTOW	< 2kg
	Payload	250g
	Range	100km
	Cruise speed	50km/h
	Wind	up to 45km/h
	Photo	5 to 10cm resolution
	Video	20cm resolution
	Infra-red video	30cm resolution
	Real-time transmission	up to 15km. Extension to
		100km
	Autopilot	Delair-Tech technology
	Onboard computer	payload and
		communication control,
		1GHz
	Field deployment	< 10 minutes
	Price	15 k€

See http://interfacedesignforgames.blogspot.fr/2010/04/week-10-uml.html for details.improvement for aeronautical engineers which significantly changes the way aeronautical systems are designed and produced.

See http://www.rockwellcollins.com/Landing/Convergence/-UASin-civil-airspace.aspx for details.

DGAC: « Direction Générale de l'Aviation Civile » which is equivalent to FAA (Federal Aviation Administration) or EASA (European Aviation Safety Agency) but at a French scale.

DELAIR TECH company website: www.delair-tech.com/

See http://boundarydevices.com/products/sabre-lite-imx6-sbc/ for details about implementation features.


Yi Ren
email: yi.ren@labri.fr

Aurélie Bugeau
email: aurelie.bugeau@labri.fr

Jenny Benois-Pineau
email: jenny.benois-pineau@labri.fr

Visual object retrieval by graph features

et image, modèles graphiques, réseaux de capteurs, graphes de terrains -T4.6 Indexation Problème traité -Object and Image retrieval Originalité -Visual object retrieval using graph features Résultats -Our approach addresses the well-known problem of adding spatial information to the standard bag-of-visual-words (BoVW) approach. To that end, a set of graphs descriptors are constructed for the entire image or for local image regions. These descriptors are then incorporated into a bag-of-visual-words approach, leading to a method called bag-of-bag-of-visual-words (BBoVW).

Introduction

This paper presents an object retrieval system based on the bag-of-visual-words (BoVW) approach [START_REF] Sivic | Video google : a text retrieval approach to object matching in videos[END_REF]. It is well known that this method does not embed any spatial information in the image representation. In this paper, we propose to incorporate such information through the representation of an image by a set of graphs. The proposed approach works as follows : first, the feature points of an image are partitioned into several graphs by minimizing an energy via graph-cuts. Using a codebook computed from all the feature points in a database, a histogram is built for each graph by assigning each of its features to the closest word in the codebook. Hence, an image being composed of k graphs is characterized by a set of k histograms. We refer to this technique as bagof-bag-of-visual-words. In order to compare two images, a similarity measure that relies on the computation of distances between graphs is finally designed. Our initial experiments show improvements over the original BoVW for certain object categories in which feature points are more stable.

Related works

Indexing methods Recent methods in the domain of image indexing all rely on the BoVW model [START_REF] Sivic | Video google : a text retrieval approach to object matching in videos[END_REF]. The idea, borrowed from document processing, is to compute a visual dictionary or codebook from all the feature points in a database, and then represent each descriptor by an index referring the most similar visual word in the vocabulary. Since the final image representation is made by computing a histogram of visual words occurrences, image features are therefore considered as independent and orderless, thus ignoring any spatial relationship between them. However, spatial information has shown to be very useful in tasks like image retrieval, image classification, and video indexing. For that reason, several works can be found in the literature that have tackled this issue [START_REF] Karaman | Indexation de la vidéo portée : application à l`étude épidémiologique des maladies liées à l`âge[END_REF][START_REF] Lazebnik | Beyond bags of features : Spatial pyramid matching for recognizing natural scene categories[END_REF]. Graph-based image representation Graphs are powerful and versatile tools that are useful for representing patterns in computer vision and pattern recognition applications. When graphs are used to represent an image, measuring the similarities between images becomes equivalent to finding similar patterns inside a series of graphs that represent those images. In this case, representing kinds of patterns by attributed graphs is extremely convenient and have been vastly investigated [START_REF] Bunke | Towards the unification of structural and statistical pattern recognition[END_REF][START_REF] Gibert | Graph embedding in vector spaces by node attribute statistics[END_REF].

3 Representing an image by a set of graphs Feature points selection First, feature points are extracted on the whole image or on the mask of the object being retrieved. We use SURF descriptors [START_REF] Bay | Surf : Speeded up robust features[END_REF] in our experiments. In some cases, the extracted points may be very close to each other, what will lead to too small triangles preventing from suitable triangulations. To avoid that, we filter the feature points by preserving only the most pertinent keypoint over any 10-pixels diametral region. After filtration, we obtain a set of filtered keypoints P = {p 1 , ..., p n } (see figure 1(b)). Constructing the set of graphs Let us denote G = (V, E) as a graph generated by the Delaunay triangulation. The vertices set V contains all the feature points : V = P. The edges set E contains all unordered pairs of points {p i , p j } that are neighbours in the Delaunay graph. We want to separate graph G into k smaller graphs using graph-cuts. This can be formulated as a labeling problem : given a points set P in image I, and a label set L = {l 1 , l 2 , ..., l k }, for each p ∈ P, we are looking for its label l(p) = l p ∈ L. In order to be consistent with the image content, we construct a set of sub-graphs {g 1 I , ..., g k I }, according to the following requirements : each sub-graph, i) should be as compact as possible ; ii) should have, as much as possible, a uniform color. To solve this labeling problem, we minimize, via graph-cuts, an energy function containing a data term and a smoothness term :

E(L) = E data (L) + E smoothness (L) = p∈S D(p, ℓp) + λ • (p,q)∈E Vp,q(ℓp, ℓq) (1)
The first term is called the data term. It is only applied to seed points p ∈ S. Seed points S ⊂ P, are user-defined hard constraints imposing on graph cuts initialization. The keypoints that are more prominent in P will be prior to be selected. Moreover, to ensure that seeds with different labels will fall into heterogeneous regions in the image, we set both color threshold and distance threshold empirically to differentiate between chosen seeds (see figure 1(c)). For the i th seed point p i ∈ S, the data term is defined as :

D(pi, ℓ) = 0 if ℓ = ℓi and ∞ otherwise.
The second term V p,q is the smoothness term. To follow the pre-stated requirements, we will encourage that any two neighbouring nodes (p, q) ∈ E are i) spatially close to each other ; ii) if node p and q have similar colors, they tend to have the same label. Hence, V p,q is composed of a color term f c (p, q) and a distance term f d (p, q) : Vp,q(ℓp, ℓq) = fc(p, q)f d (p, q)(1δ(ℓp, ℓq))

where δ(ℓp, ℓq) is the Kronecker's delta : δ(ℓp, ℓq) = 0 if ℓp = ℓq and 1 if ℓp = ℓq. The color term is given by

fc(p, q) = exp -λ1( Īp -Īq)Σ -1 c ( Īp -Īq) T (3)
where Īp = ( Ȳp, Ūp, Vp) is a mean color vector in YUV color space, computed over a 4-connected 5× 5 region centred on p. We use the YUV color space in order to have independent color channels. The covariance matrix Σ c is therefore considered diagonal. It is computed as, for all channels, the mean of the mean color vector of all nodes. Denoting p = (x p , y p ) as the coordinates of node p, the distance term is defined as

f d (p, q) = exp -λ2(p -q)Σ -1 d (p -q) T . ( 4
)
The covariance matrix Σ d is also diagonal. It is computed as the mean distance of all neighbouring points in the graph G.

The labeling of each node is finally obtained by minimizing (1) with α-expansion [START_REF] Boykov | An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision[END_REF]. A result is shown on (figure 1(e)).

The "Bag-of-bag-of-visual-words" Strategy

This section overviews our bag-of-bag-of-words object retrieval engine. The codebook is first computed using k-means clustering method over all descriptors of the filtered keypoints from the whole images in a learning database. The codewords C then correspond to the centres of the learned clusters. A bag of visual word representation, i.e. a histogram of word frequencies, is then assigned to each subgraph. Therefore, given an image I, its sub-graph g i I has its own signature H i I computed using only the SURF descriptors of its nodes. The histograms set of

I is H = {H 1 I , • • • , H k I }.
A (dis)similarity measure between two graphs can be easily computed as we just need to compare two histograms. We here adopt the idea of RootSIFT [START_REF] Arandjelović | Three things everyone should know to improve object retrieval[END_REF] by first L1 normalizing the histograms and then compute the histogram intersection of them. Nevertheless, we still need to compute the similarity between two images, knowing that they both contain k graphs. We have experimented different strategies to combine the k × k distances between a pair of query image I 1 , and database image I 2 from their corresponding histogram sets H I1 and H I2 : maximum, resp. minimum, resp. sum, etc. of all distances. Our experiments have shown a better behavior with :

d(I 1 , I 2 ) = k i=1 min j={1,...,k} {1 - C b=1 min(H i 1 (b), H j 2 (b))}.

Experimental Results

Database The SIVAL benchmark is used for the experiments. It includes 25 different image categories with 60 images per category. This benchmark emphasizes the task of localized Content-Based Image Retrieval. It allows to clearly identify the content of images for which the method has good performance, and for which it does not.

Performance is measured by calculating precision, recall, and the Mean Average Precision (MAP) over each category, since that mixing of all categories has no sense for disparity of the object appearance across categories. Our results are compared with the classical BoVW representation built on the same set of feature points that the initial graphs were built on.

For three categories : 'stripednotebook', 'goldmedal', 'woodrollingpin' among 25 categories, the proposed BBoVW method performs better than BoVW. The example of results for a "good" category and a "bad" category are presented in figure 2. The mean improvement of MAP on the three relevant categories is of 8%. As for "bad " categories, the discrepancy of results is too high to make a meaningful statistics. The method is sensitive to the stability of feature points and also needs further development for robust energy terms.

Conclusion

In this paper, we have presented a novel method to improve the orderless bag-of-words model. We combine the bag-of-words histograms with graph features at decision level, thus spatial information is injected by graph descriptors. The experimental results on SIVAL dataset showed that the method is applicable for the classes of images with stable feature points and that further research is needed for identification of more stable energy potentials. This is the focus of our actual work.

1 -

 1 Graph construction. (a) Initial SURF keypoints. (b) Filtered keypoints. (c) Seeds selection. (d) Delaunay triangulation over filtered feature points. (e) Graph-cuts result. Keypoints Triangulation Next, a Delaunay triangulation is performed over the set P. A connected graph is then generated for each image (figure 1(d)). It is composed of triangles built according the Delaunay constraint, i.e. by maximizing the minimal angle of the triangulation. Using this process, the spatial relationship between local features is invariant to image translation, scaling, and rotation.

2 -

 2 Comparision between BoW and BBoW on SIVAL benchmark. (a) "good" category : 'stripednotebook'. (b) graph descriptors from 'stripednotebook'. (c) "bad" category : 'checkeredscarf'. (d) graph descriptors from 'checkeredscarf'.