International audience

The ability to obtain a compact description of an object and to keep the significant information can be crucial for many applications such as indexing, clustering and classification. Formal concept analysis (FCA) provides an algorithm to perform such dimension reduction. However, the requirements of FCA limit its performance. In order to relax FCA requirements, this paper presents an extension of FCA with the definition and formal analysis of a fuzzy precedence graph. This is completed by a fuzzy dimension reduction algorithm. We have tested our algorithm on several real datasets related to bag of visual words and evaluated it for a classification task. The proposed formalism and algorithm improve FCA tools on several cases while retaining the significant information. Furthermore, the fuzzy dimension reduction algorithm never performs worse than FCA tools in terms of dimension reduction. We have also compared it with PCA dimension reduction. PCA usually reduces more attributes but looses more information and does so in an unreliable/unstable manner compared to our algorithm.

We present eBDtheque, a database of various comic book images and their ground truth for panels, balloons and text lines plus semantic annotations. The database consists of a hundred pages of various comic book albums, Franco-Belgian, American comics and mangas. Additionally, we present the piece of software used to establish the ground truth and a tool to validate results against this ground truth. Everything is publicly available for scientific use on http://ebdtheque.univ-lr.fr.

To reduce the gap between pixel data and thesaurus semantics, this paper presents a novel approach using mapping between two ontologies on images of drop-capitals (also named drop caps or lettrines): In the first ontology, each drop cap image is endowed with semantic information describing its content. It is generated from a database of lettrines images - namely Ornamental Letter Images Data Base - manually populated by historians with drop cap images annotations. For the second ontology we have developed image processing algorithms to extract image regions on the basis of a number of features. These features, as well as spatial relations, among regions form the basis of the ontology. The ontologies are then enriched by inference rules to annotate some regions to automatically deduce their semantics. In this article, the method is presented together with preliminary experimental results and an illustrative example.

Galois lattices' (GLs) definition is defined for a binary table (called context). Therefore, in the presence of continuous data, a discretization step is needed. Discretization is classically performed before the lattice construction in a global way. However, local discretization is reported to give better classification rates than global discretization when used jointly with other symbolic classification methods such as decision trees (DTs). We present a new algorithm performing local discretization for GLs using the lattice properties. Our local discretization algorithm is applied iteratively to particular nodes (called concepts) of the GL. Experiments are performed to assess the efficiency and the effectiveness of the proposed algorithm compared to global discretization.

This paper deals with a supervised classification method, using Galois Lattices based on a navigation-based strategy. Coming from the field of data mining techniques, most literature on the subject using Galois lattices relies on selection-based strategies, which consists of selecting/choosing the concepts which encode the most relevant information from the huge amount of available data. Generally, the classification step is then processed by a classical classifier such as the k-nearest neighbors rule or the Bayesian classifier. Opposed to these selection-based strategies are navigation-based approaches which perform the classification stage by navigating through the complete lattice (similar to the navigation in a classification tree), without applying any selection operation. Our approach, named Navigala, proposes an original navigation-based approach for supervised classification, applied in the context of noisy symbol recognition. Based on a state of the art dealing with Galois Lattices classification based methods, including a comparison between possible selection and navigation strategies, this paper proposes a description of NAVIGALA and its implementation in the context of symbol recognition. Some objective quantitative and qualitative evaluations of the approach are proposed, in order to highlight the relevance of the method.

In this paper, we propose a new approach for symbol recognition using structural signatures and a Galois lattice as a classifier. The structural signatures are based on topological graphs computed from segments which are extracted from the symbol images by using an adapted Hough transform. These structural signatures-that can be seen as dynamic paths which carry high-level information-are robust toward various transformations. They are classified by using a Galois lattice as a classifier. The performance of the proposed approach is evaluated based on the GREC'03 symbol database, and the experimental results we obtain are encouraging.

Closure systems on a set S arises in many areas as relational databases, data-mining, formal concept analysis, artificial intelligence, logical programming or lattice theory. Implicational systems represent an efficient and convenient tool to deal with a closure system, and have been studied in various areas, with different terminology. This paper states the equality between five implicational systems issued from different works and satisfying various properties. The three main properties are the directness, canonical and minimality properties, thus the name canonical direct implicational basis given to this unique implicational system. This paper also gives the link between the canonical direct implicational basis and the Horn functions (via the prime implicants). It concludes by the necessity to compare more closely related works made independently, and with different terminology in order to take advantage of the results really new

This paper presents a theoretical study on the bandwidth reservation problem for ad hoc networks. The proposed model is based on the spatial reuse and the existence of interferences. We show that in that case, the bandwidth reservation problem is NP-complete and we provide some bounds that compare solutions of the problems derived with greedy heuristics with an optimal one. We conclude with a discussion on the practical aspect of this model and its potential use in a practical protocol.