The presented work concerns the automatic detection of legend texts inside maps. After extracting the texts from the images using OCR tools, we use an iterative clustering process on the extracted texts. We consider five main criteria, with different levels of importance: text alignment, distance between text boxes, background color of the text, font color, and font size. For each criterion, we define appropriate similarity measures. We propose a method that combines, incrementally, the partitions obtained by each criterion. The experimental study reveals two important results. First, combining several criteria gives better results than considering a single distance metric (e.g., Euclidean distance) between text boxes. Secondly, the overall effectiveness of the priority relation, which we intuitively defined among the criteria for detecting caption texts, is confirmed.

This paper presents a method for the automatic extraction of the structure of wastewater networks from geographical maps, as well as their representation in the form of graphs. The approach consists first in detecting the different important elementary elements composing a wastewater network, such as the manholes, their identifiers (using optical character recognition, OCR), and the wastewater pipes that connect them. Detecting these elementary elements is a first difficult problem, despite many existing tools, mainly due to the quality of the wastewater network maps used. However, the challenge addressed in this paper is how to select the relevant elementary elements detected, and bring them together to finally extract the wastewater network. One of the main contributions of this paper is to propose an efficient algorithm to solve these selection and assignment problems (e.g., manhole identifiers to manholes represented by circles). We also deal with the situation of isolated nodes to have the most connected clusters possible. The experimental results conducted on real map data show very promising results despite the low quality of the maps.

Min-based (or qualitative) possibilistic networks are important tools to efficiently and compactly represent and analyze uncertain information. Inference is a crucial task in min-based networks, which consists of propagating information through the network structure to answer queries. Exact inference computes posteriori possibility distributions, given some observed evidence, in a time proportional to the number of nodes of the network when it is simply connected (without loops). On multiply connected networks (with loops), exact inference is known as a hard problem. This paper proposes an approximate algorithm for inference in min-based possibilistic networks. More precisely, we adapt the well-known approximate algorithm Loopy Belief Propagation (LBP) on qualitative possibilistic networks. We provide different experimental results that analyze the convergence of possibilistic LBP.

DL-Lite is one of the most important tractable fragment of DLs that provides a powerful framework to compactly encode available knowledge with a low computational complexity of the reasoning process. In semantic web area, merging different and often conflicting sources of information, has been recognized as an important problem. Pieces of information to be combined are provided with uncertainty due for instance to the reliability of sources. Possibility theory offers an important tool for representing and reasoning with uncertain, partial and inconsistent pieces of information. This paper first presents possibilistic DL-Lite, denoted by π-DL-Lite as an extension of DL-Lite within a possibility theory setting. It then focuses on the use of a minimum-based (min-based) operator, well known as idempotent conjunctive operator to combine π-DLLite possibility distributions and it shows that the semantic fusion of π-DL-Lite possibility distributions has a natural syntactic counterpart when dealing with π-DL-Lite knowledge bases. The min-based fusion operator is recommended when distinct sources that provide information are dependent.

Possibilistic networks are graphical models particularly suitable for representing and reasoning with uncertain and incomplete information. According to the underlying interpretation of possibilistic scales, possibilistic networks are either quantitative (using product-based conditioning) or qualitative (using min-based conditioning). Among the multiple tasks, possibilitic models can be used for, classification is a very important one. In this paper, we address the problem of handling uncertain inputs in binary possibilistic-based classification. More precisely, we propose an efficient algorithm for revising possibility distributions encoded by a naive possibilistic network. This algorithm is suitable for binary classification with uncertain inputs since it allows classification in polynomial time using several efficient transformations of initial naive possibilistic networks. © 2009 Wiley Periodicals, Inc.

From a knowledge representation point of view, it may be interesting to distinguish between (i) what is potentially possible because it is not inconsistent with the available knowledge on the one hand, and (ii) what is actually possible because it is reported from observations on the other hand. Such a distinction also makes sense when expressing preferences, to point out positively desired choices among merely tolerated ones. Possibility theory provides a representation framework where this distinction can be made in a graded way. The two types of information can be encoded by two types of constraints expressed in terms of necessity measures and in terms of so-called guaranteed possibility functions. These two set-functions are min-decomposable with respect to conjunction and disjunction, respectively. This gives birth to two forms of possibilistic logic bases, where clauses (resp., phrases) are weighted in terms of a necessity measure (resp., a guaranteed possibility function). By application of a minimal commitment principle, the two bases induce a pair of possibility distributions at the semantic level, for which a consistency condition should hold to ensure that what is claimed to be actually possible is indeed not impossible. The paper provides a survey of this bipolar representation framework, including the use of conditional measures, or the handling of comparative context-dependent constraints. The interest of the framework is stressed for expressing preferences, as well as in the representation of “if–then” rules in terms of examples and counterexamples. © 2008 Wiley Periodicals, Inc.

Recently, several approaches have been proposed to merge possibly contradictory belief bases. This paper focuses on max-based merging operators applied to incommensurable ranked belief bases. We first propose a characterization of a result of merging using Pareto-like ordering on a set of possible solutions. Then we propose two equivalent ways to recover the result of merging. The first one is based on the notion of compatible rankings defined on finite scales. The second one is only based on total pre-orders induced by ranked bases to merge.

This paper deals with iterated belief change. Epistemic states are suitable to represent an intelligent agent's knowledge. Most of the time, when dealing with geographic information, the agent faces incomplete, uncertain, or inaccurate information and needs a mechanism for either revision, update, or fusion to handle their change in beliefs in the presence of new items of information. After some preliminaries on the representation of epistemic states by means of pre-orders, the paper presents three approaches to belief change: revision, update, and fusion. For each of these approaches, the background, postulates, representation by pre-orders, and semantic and syntactic requirements are given. In each case, the approaches are illustrated by examples.

Modeling information security policies is an important problem in many domains. This is particularly true in the health care sector, where information systems often manage sensitive and critical data. This article proposes to use nonmonotonic reasoning systems to control access to sensitive data in accordance with a security policy. In the first part of the article, we propose an access control model that overcomes several limitations of existing systems. In particular, it allows us to deal with contexts and to represent the two main kinds of privileges: permissions and prohibitions. This model will then be formally encoded using stratified (or prioritized) first-order knowledge bases. In the second part of the article, we discuss the problem of conflicts due to the joint handling of permissions and prohibitions. We show that approaches proposed for solving conflicts in propositional knowledge bases are not appropriate for handling inconsistent first-order knowledge bases. © 2004 Wiley Periodicals, Inc. Int J Int Syst 19: 817–836, 2004.

This example considers the problem of finding a suitable assignment of a set of referees to each one of a set of papers submitted to a conference, given the preferences expressed by the referees regarding the papers they are willing to review, the adequation between their areas of competence and the topics of the papers, and a set of regulations bearing on the global assignment. This example illustrates the issue of fusing heterogeneous data consisting of individual preference profiles and a set of global regulations. © 2001 John Wiley & Sons, Inc.

The problem of combining pieces of information issued from several sources can be encountered in various fields of application. This paper aims at presenting the different aspects of information fusion in different domains, such as databases, regulations, preferences, sensor fusion, etc., at a quite general level. We first present different types of information encountered in fusion problems, and different aims of the fusion process. Then we focus on representation issues which are relevant when discussing fusion problems. An important issue is then addressed, the handling of conflicting information. We briefly review different domains where fusion is involved, and describe how the fusion problems are stated in each domain. Since the term fusion can have different, more or less broad, meanings, we specify later some terminology with respect to related problems, that might be included in a broad meaning of fusion. Finally we briefly discuss the difficult aspects of validation and evaluation. © 2001 John Wiley & Sons, Inc.