Cassia Trojahn
email: cassia.trojahn@inrialpes.fr

Jérôme Santos

Valentina Euzenat

Terry Tamma

Payne

Cássia Trojahn

Jérôme Euzenat
email: jerome.euzenat@inrialpes.fr

Valentina Tamma
email: v.tamma@liverpool.ac.uk

Terry R Payne
email: t.r.payne@liverpool.ac.uk

Cássia Trojahn

Argumentation for reconciling agent ontologies

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

The problem of dynamic reconciliation of vocabularies, or ontologies, used by agents during interactions has recently received significant attention, motivated by the growing adoption of service-oriented and distributed computing. In such scenarios, agents are situated in open environments and may encounter unknown agents offering new services due to changes in a user's context or goal. These multi-agent systems are, by nature, distributed and heterogeneous, and as such, ontologies play a fundamental role in formalising the concepts that agents perceive, share, or encounter. However, as the heterogeneity that permeates these environments increases, fewer assumptions on the vocabulary and content of these ontologies can be made, hindering seamless interactions between the agents. Thus, mechanisms that can dynamically and autonomously reconcile the differences between ontologies are essential if agents are to communicate within such open and evolving environments.

Early systems avoided the problem of ontological heterogeneity by relying on the existence of a shared ontology, or simply assuming that a canonical set of ontology correspondences (possibly defined at design time) could be used to resolve ontological mismatches. However, such assumptions work only when the environment is (semi-) closed and carefully managed, and no longer hold in open environments where a plethora of ontologies exist. Moreover, the assumption of a common ontology forces an agent to comply with a fixed, but highly constrained view of the world, with respect to a set of predefined tasks and, as a consequence, abandon its own world view, which may have evolved due to interactions with other agents [START_REF] Van Diggelen | ANEMONE: An effective minimal ontology negotiation environment[END_REF].

To facilitate the communication between two agents, they first need to establish a set of correspondences (or an alignment) between their respective ontologies. The reconciliation of heterogeneous ontologies has been investigated at length by research efforts in ontology matching [START_REF] Euzenat | Ontology matching[END_REF], which tries to determine suitable correspondences between two ontologies. However the increased availability of mechanisms for ontology matching has facilitated the potential construction of a plethora of different correspondence sets between two ontologies, depending on the approach used. In addition, the majority of traditional matching approaches cannot be easily utilised as part of dynamic interaction protocols since they either require human intervention or they align the ontologies at design time. Even when alignments are pre-computed and stored within some alignment library, the selection of a possible correspondence that would be mutually acceptable to two transacting agents can be problematic, as the choice of correspondences can be highly dependent on the current task or available knowledge. For example, an agent may prefer correspondences which have been approved by its own institution and another one may prefer a correspondence designed for the same task. These may not be easy to reconcile. Hence, some correspondences may be preferable to some agents, but may be unsuitable or untrustworthy to others. In addition, it may not always be desirable for an agent to disclose a preference for a given type of correspondence as this may reveal its goal, and thus compromise it's ability to negotiate strategically with other agents within a competitive environment. Thus it is not always possible to utilise a collaborative approach, or exploit the use of a third party mediator to determine a mutually acceptable set of correspondences.

The agreement on a mutually acceptable alignment is an important problem that therefore arises when different parties need to reconcile private, yet potentially conflicting preferences over candidate correspondences. Such an agreement can be achieved through a negotiation process whereby agents iteratively exchange proposals and counter-proposals [START_REF] Parsons | Negotiation through argumentation-A preliminary report[END_REF][START_REF] Jennings | Automated negotiation: Prospects methods and challenges[END_REF] until some consensus is reached. Argumentation can be seen as a qualitative negotiation model based on the construction and comparison of arguments [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF][START_REF] Prakken | Argument-based extended logic programming with defeasible priorities[END_REF][START_REF] Amgoud | A reasoning model based on the production of acceptable arguments[END_REF], either supporting or refuting a set of possible propositions. Thus, by considering these propositions as correspondences (with justifications that support their use), agents can strategically argue in favour of (or against) possible correspondences given their individual strategies or preferences.

This chapter presents an overview on the approaches for alignment agreement based on argumentation. The different approaches are presented following two scenarios. In the first one, agents with different preferences need to agree on the alignment of their ontologies in order to communicate with each other. For the second scenario, specialised matcher agents rely on different matching approaches and argue on their individual results in order to obtain a consensual alignment.

The remainder of this chapter is structured as follows. First, we provide the basic definitions of ontology matching and argumentation frameworks ( §2). Next, two argumentation frameworks for alignment agreement are introduced ( §3). The different proposals on argumentation for alignment agreement are then presented ( §4). The limitations and challenges in this domain are discussed ( §5). Finally, related work ( §6) and final remarks ( §7) are presented.

2 Foundations: Alignment and Argumentation Frameworks

Ontology matching

An ontology typically provides a vocabulary describing a domain of interest and a specification of the meaning of terms in that vocabulary. As different agents within an open multi-agent system may be developed independently, they may commit to different ontologies to model the same domain. Whilst these different ontologies may be similar, they may differ in granularity or detail, use different representations, or model the concepts, properties and axioms in different ways.

In order to illustrate the matching problem, let us consider an e-Commerce marketplace, where two agents, a buyer and a seller, need to negotiate the price of a digital camera. Before starting the negotiation, they need to agree on the vocabulary to be used for exchanging the messages. They use the ontologies o and o ′ , respectively (Figure 1). These ontologies contain subsumption statements (e.g., DigitalCamera ⊑ Product), property specifications (e.g., price domain Product) and instance descriptions (e.g., ThisCamera price 250$).

Ontology matching is the task of finding correspondences between ontologies. Correspondences express relationships supposed to hold between entities in ontologies, for instance, that an Electronic in one ontology is the same as a Product in another one or that DigitalCamera in an ontology is a subclass of CameraPhoto in another one. In the example above, one of the correspondences expresses an equivalence, while the other one is a subsumption correspondence. A set of correspondences between two ontologies is called an alignment. An alignment may be used, for instance, to generate query expressions that automatically translate instances of these ontologies under an integrated ontology or to translate queries with respect to one ontology in to query with respect to the other. Matching determines an alignment A ′ for a pair of ontologies o and o ′ . There are other parameters that can extend the definition of the matching process, namely: (i) the use of an input alignment A, which is to be completed by the process; (ii) the matching parameters, for instance, weights, thresholds, etc.; and (iii) external resources used by the matching process, for instance, common knowledge and domain specific thesauri.

o o ′ A matching A ′
parameters resources Fig. 2 The ontology matching process (from [START_REF] Euzenat | Ontology matching[END_REF]).

Each of the elements featured in this definition can have specific characteristics which influence the difficulty of the matching task. As depicted in Figure 2, the matching process receives as input three main parameters: the two ontologies to be matched (o and o ′ ) and the input alignment (A). The input ontologies can be characterized by the input languages they are described (e.g., OWL-Lite, OWL-DL, OWL-Full), their size (number of concepts, properties and instances) and complexity, which indicates how deep is the hierarchy structured and how dense is the interconnection between the ontological entities. Other properties such as consistency, correctness and completeness are also used for characterizing the input ontologies. The input alignment (A) is mainly characterized by its multiplicity (or cardinality, e.g., how many entities of one ontology can correspond to one entity of the others) and coverage in relation to the ontologies to be matched. In a simple scenario, the input alignment is empty. Regarding the parameters, some systems take advantage of external resources, such as WordNet, sets of morphological rules or previous alignments of general purpose (Yahoo and Google catalogs, for instance).

Different approaches to the problem of ontology matching have emerged from the literature [START_REF] Euzenat | Ontology matching[END_REF]. The main distinction between each is due to the type of knowledge encoded within each ontology, and the way it is utilized when identifying correspondences between features or structures within the ontologies. Terminological methods lexically compare strings (tokens or n-grams) used in naming entities (or in the labels and comments concerning entities), whereas semantic methods utilise model-theoretic semantics to determine whether or not a correspondence exists between two entities. Approaches may consider the internal ontological structure, such as the range of their properties (attributes and relations), their cardinality, and the transitivity and/or symmetry of their properties, or alternatively the external ontological structure, such as the position of the two entities within the ontological hierarchy. The instances (or extensions) of classes could also be compared using extension-based approaches. In addition, many ontology matching systems rely not on a single approach.

The output alignment A ′ is a set of correspondences between o and o ′ . Generally, correspondences express a relation r between ontology entities e and e ′ with a confidence measure n. These are abstractly defined in [START_REF] Euzenat | Ontology matching[END_REF]. In this chapter, we will restrict the discussion to simple correspondences. Definition 1 (Simple correspondence). Given two ontologies, o and o ′ , a simple correspondence is a quintuple: id, e, e ′ , r, n , such that:

• id is a URI identifying the given correspondence; • e and e ′ are named ontology entities, i.e., named classes, properties, or instances; • r is a relation among equivalence (≡), more general (⊒), more specific (⊑), and disjointness (⊥); • n is a number in the [0, 1] range.

The correspondence id, e, e ′ , n, r asserts that the relation r holds between the ontology entities e and e ′ with confidence n. The higher the confidence value, the higher the likelihood that the relation holds. Alignments may have different cardinalities; 1:1 (one-to-one), 1:m (one-to-many), n:1 (many-to-one) or n:m (many-tomany). An alignment is a 1:1 alignment, if and only if no two different entities in one of the ontologies are matched to the same entity in the other ontology.

Mechanisms that facilitate the construction of alignments require access to both ontologies. Whilst it may be desirable to embed such mechanisms within agents that operate in transparent and collaborative environments, exposing one's ontology may not always be desirable in competitive or adversarial environments, as this may allow other agents to infer, and exploit this knowledge in subsequent negotiations. In addition, creating alignments can be costly, and thus the ability to cache or save previously generated alignments (possibly generated by trusted third parties) may be desirable. Thus, agents may rely on an external alignment service.

For example, the Alignment server, built on the Alignment API [START_REF] Euzenat | An API for ontology alignment[END_REF], provides functionality to facilitate ontology matching, as well as storing and retrieving alignments. In addition, it can provide assistance to agents when attempting to determine relationships between their ontologies, so that they can understand and interpret each other's messages. An agent plug-in has been developed to allow agents based on the JADE/FIPA ACL (Agent Communication Language) to interact with the server in order to retrieve alignments. Such a service can provide alignments over which the agents will argue in order to choose the more suitable correspondences. Alignments, and the correspondences within such alignments, can be better qualified, through the inclusion of metadata, which may refer to the provenance and origin of alignments, confidence ratings, and the original purposes for which they were created. Other metadata may also include any manual (human-based) checks or endorsements provided by some authority. This type of metadata is used, for instance, by Bioportal [START_REF] Noy | Bioportal: ontologies and integrated data resources at the click of a mouse[END_REF], which is an alternative alignment web-service, where users can select correspondences based on providence-based alignment metadata.

Argumentation frameworks

Argumentation is a decentralised, peer-based negotiation model for reasoning based on the construction and comparison of arguments. The central notion in argumentation systems is the notion of acceptability. Different argumentation frameworks have been specified presenting different notions of acceptability. The classical argumentation framework (AF) was proposed by Dung [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF], whose notion of acceptability defines that an argument should be accepted only if every attack on it is attacked by an accepted argument. Dung defines an argumentation framework as follows:

Definition 2 (Argumentation Framework [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF]). An Argumentation Framework (AF) is a pair A, ⋉ , such that A is a set of arguments and ⋉ (attacks) is a bi- The key question about the framework is whether a given argument a ∈ A should be accepted or not. Dung proposes that an argument should be accepted only if every attack on it is attacked by an accepted argument. This notion then leads to the definition of acceptability (for an argument), admissibility (for a set of arguments) and preferred extension: Definition 3 (Acceptable argument [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF]). An argument a ∈ A is acceptable with respect to set arguments S, noted acceptable(a, S), iff ∀x ∈ A, (x ⋉ a -→ ∃y ∈ S, y ⋉ x).

Definition 4 (Conflict-free set [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF]). A set S of arguments is conflict-free iff ¬∃x, y ∈ S, x ⋉ y. A conflict-free set of arguments S is admissible iff ∀x ∈ S, acceptable(x, S).

Definition 5 (Preferred-extension [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF]). A set of arguments S is a preferred extension iff it is a maximal (with respect to inclusion set) admissible set of A.

Thus, a preferred extension represents a consistent position within an argumentation framework, which defends itself against all attacks and cannot be extended without raising conflicts.

In Dung's framework, all arguments have equal strength, and therefore attacks always succeed. This is reasonable when dealing with deductive arguments, but in many domains, arguments may lack some coercive force: they provide reasons which may be more or less persuasive. For that purpose, preference-based argumentation has been designed [START_REF] Amgoud | On the acceptability of arguments in preference-based argumentation[END_REF] which assigns preferences to arguments, so that preferred arguments would successfully attack less preferred ones (but not vice versa). Bench-Capon [START_REF] Bench-Capon | Persuasion in practical argument using value-based argumentation frameworks[END_REF] went one step further with the Value Based Argumentation framework (VAF1 ), which assigns to arguments the values they promote. Agents are distributed among different audiences which ascribe different preferences to such values. Hence, different audiences will have different preferences among the arguments and similarly, successful attacks for an audience are those made by arguments of highest values to the audience.

Definition 6 (Value-based AF [6]). A Value-based Argumentation Framework (VAF) is a quintuple A, ⋉, V, v, such that A, ⋉ is an argumentation framework, V is a nonempty set of values, v : A → V, and is the preference relation over V (v 1 v 2 means that, in this framework, v 1 is preferred over v 2 ).
To each audience, α corresponds a value-based argumentation framework VAF α such that v 1 α v 2 states that audience α prefers v 1 over v 2 . Attacks are then deemed successful, based on the preference ordering on the arguments' values. This leads to re-defining the notions seen previously: Definition 7 (Successful attack [START_REF] Bench-Capon | Persuasion in practical argument using value-based argumentation frameworks[END_REF]). In a value-based argumentation framework, A, ⋉, V, v, , an argument a ∈ A defeats (or successfully attacks) an argument b ∈ A, noted a †b, iff both a ⋉ b and v(b) v(a). Definition 8 (Conflict-free set [START_REF] Bench-Capon | Persuasion in practical argument using value-based argumentation frameworks[END_REF]). A set S of arguments is conflict-free for an audience α iff ∀x, y ∈ S, ¬(x ⋉ y) ∨ v(y) α v(x).

Acceptable arguments and preferred extensions are defined as before. In order to determine preferred extensions with respect to a value ordering promoted by distinct audiences, objective and subjective acceptance are defined. An argument is subjectively acceptable if and only if it appears in some preferred extension for some specific audience. An argument is objectively acceptable if and only if it appears in all preferred extension for every specific audience.

Argumentation Frameworks for Alignment Agreement

In alignment agreement, arguments can be seen as positions that support or reject correspondences. Such arguments interact following the notion of attack and are selected according to the notion of acceptability. Argumentation frameworks for alignment agreement redefine the notion of acceptability, taking into account the confidence of the correspondences and the number of agents agreeing on a correspondence. In this section we first introduce the general definition of argument, which will be extended according to the scenario where argumentation is used ( §4), and then we present the argumentation frameworks.

Arguments on correspondences

The different approaches presented below all share the same notion of correspondence argument originally defined in [START_REF] Laera | Reaching agreement over ontology alignments[END_REF]. The general definition of correspondence argument is as follows: Definition 9 (Argument [START_REF] Laera | Reaching agreement over ontology alignments[END_REF]). An argument a ∈ AF is a tuple a = c, v, h , such that c is a correspondence e, e ′ , r, n ; v ∈ V is the value of the argument and h is one of {+, -} depending on whether the argument is that c does or does not hold.

In this definition, the set of considered values may be based on: the types of matching techniques that agents tend to prefer; the type of targeted applications; information about various level of endorsement of these correspondences, and whether or not they have been checked manually. Thus, any type of information which can be associated with correspondences (see §2.1) may be used. For example, an alignment may be generated for the purpose of information retrieval; however, this alignment may not be suitable for an agent performing a different task requiring more precision. This agent may therefor prefer the correspondences generated by a different agent for web service composition. Likewise, another agent may prefer human curated alignments rather than alignments generated on the fly.

Arguments interact based on the notion of attack relation:

Definition 10 (Attack [START_REF] Laera | Reaching agreement over ontology alignments[END_REF]). An argument c, v, h ∈ A attacks another argument

c ′ , v ′ , h ′ ∈ A iff c = c ′ and h = h ′ .
Therefore, if a = c, v 1 , + and b = c, v 2 , -, a ⋉ b and vice-versa (b is the counter-argument of a, and a is the counter-argument of b).

Strength-based argumentation framework (SVAF)

Bench-Capon's framework acknowledges the importance of preferences when considering arguments. However, within the specific context of ontology matching, an objection can still be raised regarding the lack of complete mechanisms for handling persuasiveness. Indeed, many ontology matchers generate correspondences with a strength that reflects the confidence they have in the similarity between the two entities. These confidence levels are usually derived from similarity assessments made during the matching process, e.g., from the edit distance measure between labels, or overlap measure between instance sets, and thus are often based on objective grounds. In order to represent arguments with strength, reflecting this confidence in a correspondence, [START_REF] Trojahn | A cooperative approach for composite ontology mapping[END_REF] proposed the Strength-based Argumentation Framework (SVAF), extending Bench-Capon's VAF by redefining the notion of acceptability.

Definition 11 (SVAF [START_REF] Trojahn | A cooperative approach for composite ontology mapping[END_REF]). A strength-based argumentation framework (SVAF) is a sextuple A, ⋉, V, v, , s such that A, ⋉, V, v, is a value-based argumentation framework and s : A → [0, 1] represents the strength of the argument.

As in value-based argumentation frameworks, each audience α is associated with its own framework in which only the preference relation α differs. In order to accommodate the notion of strength, the notion of successful attack is extended: Definition 12 (Successful attack [START_REF] Trojahn | A cooperative approach for composite ontology mapping[END_REF]). In a strength-based argumentation framework A, ⋉, V, v, , s , an argument a ∈ A successfully attacks (or defeats, noted a †b)

an argument b ∈ A iff a ⋉ b ∧ (s(a) > s(b) ∨ (s(a) = s(b) ∧ v(a) v(b)))

Voting-based argumentation framework (VVAF)

The frameworks described so far assume that candidate correspondences between two entities may differ due to the approaches used to construct them, and thus these argumentation frameworks provide different mechanisms to identify correspondences generated using approaches acceptable to both agents. However, different alignment generators may often utilise the same approach for some correspondences, and thus the approach used for that correspondence may be significant. Some large-scale experiments involving several matching tools (e.g. the OAEI 2006 Food track campaign [START_REF] Euzenat | Results of the ontology alignment evaluation initiative[END_REF]) have demonstrated that the more often a given approach for generating a correspondence is used, the more likely it is to be valid. Thus, the SVAF was adapted and extended in [START_REF] Isaac | Using quantitative aspects of alignment generation for argumentation on mappings[END_REF], to take into account the level of consensus between the sources of the alignments, by introducing the notions of support and voting into the definition of successful attacks. Support enables arguments to be counted as defenders or co-attackers during an attack: Definition 13 (VVAF [START_REF] Isaac | Using quantitative aspects of alignment generation for argumentation on mappings[END_REF]). A voting-based argumentation framework (VVAF) is a septuple A, ⋉, S, V, v, , s such that A, ⋉, V, v, , s is a SVAF, and S is a (reflexive) binary relation on A, representing the support relation between arguments. S(x, a) means that the argument x supports the argument a (i.e., they have the same value of h). S and ⋉ are disjoint relations.

A simple voting mechanism (e.g. plurality voting) can be used to determine the success of a given attack, based upon the number of supporters for a given approach. Definition 14 (Successful attack [START_REF] Isaac | Using quantitative aspects of alignment generation for argumentation on mappings[END_REF]). This voting mechanism is based on simple counting. As some ontology matchers include confidence values with correspondences, a voting mechanism can exploit this confidence value, for example by simply calculating the total confidence value of the supporting arguments. However, this relies on the questionable assumption that all values are equally scaled (as is the case with the SVAF). In [START_REF] Isaac | Using quantitative aspects of alignment generation for argumentation on mappings[END_REF], a voting framework that normalised these confidence values (i.e. strengths) was evaluated, but was inconclusive. Another possibility would be to rely on a deeper justification for correspondences and to have only one vote for each justification. Hence, if several matchers considered two concepts to be equivalent because WordNet considers their identifier as synonyms, this would be counted only once.

Argumentation over Alignments

The use of argumentation has been exploited in two different scenarios presented below. In the first, agents attempt to construct mutually acceptable alignments based on existing correspondences to facilitate communication, based on their alignment preferences (which may be task specific). They therefore argue directly over candidate correspondences provided by an alignment service, with each agent specifying an ordered preference of correspondence types and confidence thresholds.

The second scenario focuses on the consensual construction of alignments involving several agents, each of which specialises in constructing correspondences using different approaches. These matching agents generate candidate correspondences and attempt to combine these to produce a new alignment through argumentation. Thus, whilst the first scenario utilises argumentation as a negotiating mechanism to find a mutually acceptable alignment between transacting agents, this latter scenario could be viewed as offering a service for negotiating alignments. [START_REF] Laera | Reaching agreement over ontology alignments[END_REF][START_REF] Laera | Agents arguing over ontology alignments[END_REF][START_REF] Laera | Argumentation over ontology correspondences in MAS[END_REF], to allow agents to propose, attack, and counter-propose candidate correspondences according to the agents' preferences, in order to identify mutually acceptable alignments. Their approach utilises Bench-Capon's VAF [START_REF] Bench-Capon | Persuasion in practical argument using value-based argumentation frameworks[END_REF] to support the specification of preferences of correspondent types (as discussed in §2.1) within each argument. Thus, when faced with different, candidate correspondences who's type differ, each agents' preference ordering can be considered when determining if an argument for one correspondence will successfully attack another. Different audiences therefore represent different sets of arguments for preferences between the categories of arguments (identified in the context of ontology matching). Each agent is defined as follows:

Definition 15 (Agent). An agent Ag i is characterised by a tuple O i , F, ǫ i , such that O i is the ontology used by the agent, F is its (valued-based) argumentation framework, and ǫ i is the private threshold value.

Candidate correspondences are retrieved from an alignment service (see §2.1) which also provides the justifications G (described below) for each correspondence, based on the approach used to construct the correspondence. The agents use this information to exchange arguments supplying the reasons for their choices. In addition, as these grounds include a confidence value associated with each correspondence, each agent utilises a private threshold value ǫ to filter out correspondences with low confidence values2 . This threshold, together with the pre-ordering of preferences, are used to generate arguments for and against a correspondence. It extends the notion of argument presented in §3.1: Definition 16 (Argument [START_REF] Laera | Reaching agreement over ontology alignments[END_REF]). An argument is a triple G, c, h , where c is a correspondence e, e ′ , r, n , G is the grounds justifying a prima facie belief that the cor-respondence does, or does not hold; and h is one of {+, -} depending on whether the argument is that c does or does not hold.

The grounds G justifying a correspondence between two entities are based on the five categories of correspondence types (as discussed in §2.1) -namely Semantic (S), Internal Structural (IS), External Structural (ES), Terminological (T), and Extensional (E). These classes are used as types for the values V, i.e., V = {M, IS, ES, T, E}, that are then used to construct an agent's partially-ordered preferences, based on the agents ontology and task. Thus, an agent may specify a preference for terminological correspondences over semantic correspondences if the ontology it uses is mainly taxonomic, or vice versa if the ontology is semantically rich. Preferences may also be based on the type of task being performed; extensional correspondences may be preferred when queries are about instances that are frequently shared. The pre-ordering of preferences for each agent Ag i is over V, corresponding to the specification of an audience. Specifically, for each candidate correspondence c, if there exists one or more justifications G for c that corresponds to the highest preferences of Ag i (with the respect of the pre-ordering), assuming n is greater than its private threshold ǫ, an agent Ag i will generate arguments x = (G, c, +). If not, the agent will generate arguments against: x = (G, c, -). The arguments interact based on the notion of attack, as specified in §3.1.

The argumentation process takes four main steps: (i) each agent Ag i constructs an argumentation framework V AF i by specifying the set of arguments and the attacks between them; (ii) each agent Ag i considers its individual frameworks V AF i with all the argument sets of all the other agents and then extends the attack relations by computing the attacks between the arguments present in its framework with the other arguments; (iii) for each V AF i , the arguments which are undefeated by attacks from other arguments are determined, given a value ordering -the global view is considered by taking the union of these preferred extensions for each audience; and (iv) the arguments in every preferred extension of every audience are consideredthe correspondences that have only arguments for are included in the a set called agreed alignments, whereas the correspondences that have only arguments against them are rejected, and the correspondences which are in some preferred extension of every audience are part of the set called agreeable alignments.

The dialogue between agents consists of exchanging sets of arguments and the protocol used to evaluate the acceptability of a single correspondence is based on a set of speech acts (Support, Contest, W ithdraw). For instance, when exchanging arguments, an agent sends Support(c, x 1 ) for supporting a correspondence c through the argument x 1 = (G, c, +) or Contest(c, x 2 ) for rejecting c, by x 2 = (G, c, -). If the agents do not have any arguments or counter-arguments to propose, then they send W ithdraw(c) and the dialogue terminates.

To illustrate this approach, consider the two agents buyer b and seller s, using the ontologies in Figure 1. First, the agents access the alignment service that returns the correspondences with the respective justifications:

• m 1 : zoom o , zoom o ′ , ≡, 1.0 , with G = {T, ES} • m 2 : Battery o , Battery o ′ , ≡, 1.0 , with G = {T } • m 3 : M emoryCard o M emory o ′ , ≡, 0.54 , with G = {T } • m 4 : brand o , brandN ame o ′ , ≡, 0.55 , with G = {T, ES} • m 5 : price o , price o ′ , ≡, 1.0 , with G = {T, ES} • m 6 : CameraP hoto o , DigitalCamera o ′ , ≡, 1.0 , with G = {ES} • m 7 : resolution o , pixels o ′ , ≡, 1.00 , with G = {ES}
Agent b selects the audience R 1 , which prefers terminology to external structure (T ≻ R1 ES), while s prefers external structure to terminology (ES ≻ R2 T ). All correspondences have a degree of confidence n that is above the threshold of each agent and then all of them are taken into account. Both agents accept m 1 , m 4 and m 5 . b accepts m 2 , m 3 , while s accepts m 6 and m 7 . Table 1 shows the arguments and corresponding attacks.

T, m 1 , + b, s B ES, m 1 , + b, s C T, m 2 , + D b D ES, m 2 , - C s E T, m 3 , + F b F ES, m 3 , - E s G T, m 4 , + b, s id argument attack agent H ES, m 4 , + b, s I T, m 5 , + b, s J ES, m 5 , + b, s L ES, m 6 , + M s M T, m 6 , - L b N ES, m 7 , + O s O T, m 7 , - N b
The arguments A, B, G, H, I, and J are not attacked and then are acceptable for both agents (they form the agreed alignment). The arguments C and D are mutually attacked and are acceptable only in the corresponding audience, i.e., C is acceptable for the audience b and D is acceptable for the audience s. The same occurs for the arguments E, F , L, M , M , and O. The correspondences in such arguments are seen as the agreeable alignments.

The approach by Trojahn and colleagues

In order to provide translations between messages in agent communication, [START_REF] Trojahn | Conjunctive queries for ontology based agent communication in MAS[END_REF] formally defines an alignment as a set of correspondences between queries over ontologies. The alignment is obtained by specialised matcher agents that argue in order to agree on a globally acceptable alignment. The set of acceptable arguments is then represented as conjunctive queries in OWL-DL [START_REF] Haase | A mapping system for the integration of OWL-DL ontologies[END_REF].

A conjunctive query has the form (P i (s i )), where each P i (s i ) represents a correspondence. For instance, CameraP hoto o , DigitalCamera o ′ , ≡, 1.0 is represented as Q(x) : CameraP hoto(x) ≡ DigitalCamera(x).

Consider the example where the agents "buyer b" and "seller s" interact to agree on the price of a digital camera, using the ontologies o and o ′ of Figure 1, respectively. Before the agents can agree on the price, they need to agree on the terms used to communicate to each other. This task can be delegated to a matcher agent m, that receives the two ontologies and sends them to an argumentation module. This module, made up of different specialised agents a 1 , ..., a n (which can be distributed on the web), receives the ontologies and returns a set of DL queries representing the acceptable correspondences. These interactions are loosely based on the Contract Net Interaction Protocol [START_REF]FIPA: Contract net interaction protocol specification[END_REF]. The argumentation process between the specialised matchers is detailed in Section 4.2. Table 2 describes the steps of the interaction between the agents.

Table 2 Interaction steps [START_REF] Trojahn | Conjunctive queries for ontology based agent communication in MAS[END_REF].

Step Description 1

Matcher agent m requests the ontologies to be matched to agents b and s 2

Ontologies are sent from m to the argumentation module 3

Matchers a 1 , ..., a n apply their algorithms 4

Each matcher a i communicate with each others to exchange their arguments 5 extensions of each a i are generated 6

Objectively acceptable arguments o are computed 7

Correspondences in o are represented as conjunctive queries 8

Queries are sent to m 9

Queries are sent from m to b and s 10 Agents b and s use the queries to communicate with each other

In fact, only one of the agents should receive the DL queries, which should be responsible for the translations. We consider that the set of objectively acceptable arguments has the correspondences shown in Figure 3, with the respective queries. 2 shows an AUML3 interaction diagram with the messages exchanged between the agents b and s during the negotiation of the price of the camera. The agents use the queries to search for correspondences between the messages sent from each other and the entities in the corresponding ontologies. In the example, the agent b sends a message to the agent s, using its vocabulary. Then, the agent s converts the message, using the DL queries.

Query ID Correspondences Q b1 (x) b:CameraPhoto(x) Q s1 (x) s:DigitalCamera(x) m 1 Q b1 ≡ Q s1 Q b2 (y) b:zoom(y) Q s2 (y) s:zoom(y) m 2 Q b2 ≡ Q s2 Q b3 (y) b:resolution(y) Q s3 (y) s:pixels(y) m 3 Q b3 ≡ Q s3

Reducing the argumentation space through modularization

Doran et al. [START_REF] Doran | Dynamic selection of ontological alignments: A space reduction mechanism[END_REF] utilised modularization to identify the ontological descriptions relevant to the communication, and consequently reduce the number of correspondences necessary to form the alignment. The use of argumentation can be computationally costly, as the complexity can reach Π (p) 2 -complete in some cases. Thus, by reducing the number of arguments, the time required for generating the alignments can be significantly reduced; even when taking into account the time necessary for the modularization process itself. In an empirical study, the authors found that the use of modularization significantly reduced the average number of correspondences presented to the argumentation framework, and hence the size of the search space -in some cases by up to 97%, across a number of different ontology pairs. They also noted that three patterns emerged: i) where no reduction in size occurred (in 4.84% of cases within the study); ii) where the number of correspondences was reduced (55.14%); and iii) where modules of size zero were found (40.02%), corresponding to failure scenarios; i.e. where the subsequent transaction would fail due to insufficient alignment between the ontologies.

An ontology modularization technique extracts a consistent module M from an ontology A that covers a specified signature Sig(M ), such as Sig(M ) ⊆ Sig(O). M is the part of O that is said to cover the elements defined by Sig(M ). The first agent engaging in the communication specifies the Sig(M ) of its ontology O where M is an ontology concept relevant for a task. The resulting module contains the entities considered to be relevant for its task, including the subclasses and properties of the concepts in Sig(M ). The step-by-step interaction between two agents, following an argumentation based on modularization is presented in Table 3.

Table 3 Ontology modularization and argumentation for alignment agreement [START_REF] Doran | Efficient argumentation over ontology correspondences[END_REF].

Step Description 1

Ag 1 asks a query, query(A ∈ Sig(O)) to Ag 2 . 2 Ag 2 does not understand the query, A / ∈ Sig(O ′ )) and informs Ag 1 they need to use a server. 3

Ag 1 produces, om(O, Sig(A)), an ontology module, M , to cover the concepts required for its task. 4

Ag 1 and Ag 2 invoke the server. Ag 1 sends its ontology, O and the signature of M , Sig(M ). 5

The alignment service aligns the two ontologies and filters the correspondences according to M . Only those features an entity from M are returned to both agents. 6

The agents begin the process of argumentation, with each agent generating arguments and counter-arguments. 7

The iteration terminates when the agents agree on a set of correspondences. 8

Ag 1 asks again Ag 2 , using the agreed correspondences,

query(A ∈ Sig(O) ∧ B ∈ Sig(O ′ ))
where A and B are aligned. 9

Ag 2 answers the query using the agreed correspondences.

For communicating, only the initiating agent (Ag 1 ) is aware of its task and, consequently, which concepts are relevant to this task (Steps 1 and 2). These concepts will be included in Sig(M ), the signature of the resulting ontology module (Step 3). The set of candidate correspondences (Step 4) is filtered (Step 5) according to the filtering function f ilter(). f ilter returns a subset Z of correspondences, where the entities e in these correspondence are in Sig(M ). The set Z is then used within the argumentation process. Modularization is therefore used to filter the correspondences that are passed to the argumentation process. The agents then argue (Steps 6-7) to reach an acceptable alignment.

The combination of argumentation and modularization reduces the cost of reaching an agreement over an alignment, by reducing the size of the set of correspondences argued over, and hence the number of arguments required. This greatly contributes to reduce the consumed time, at a minimal expense in accuracy.

Following the example of the buyer and seller agents, the buyer agent knows which concepts will be used for communicating and then a module of the ontology o is extracted containing such concepts (i.e., CameraP hoto, resolution, zoom, and price). The buyer agent then filters the correspondences in order to retrieve the subset containing only these concepts.

Solving conflicts between matcher agents

In [START_REF] Trojahn | A cooperative approach for composite ontology mapping[END_REF], alignments produced by different matchers are compared and agreed via an argumentation process. The matchers interact in order to exchange arguments and the SVAF model ( §3.2) is used to support the choice of the most acceptable of them. Each correspondence can be considered as an argument because the choice of a correspondence may be a reason against the choice of another correspondence. Correspondences are represented as arguments, extending the notion of argument specified in §3.1: Definition 17 (Argument). An argument x ∈ AF is a tuple x = c, v, s, h , such that c is a correspondence e, e ′ , r, n ; v ∈ V is the value of the argument; s is the strength of the argument, from n; and h is one of {+, -} depending on whether the argument is that c does or does not hold.

The matchers generate arguments representing their alignments following a negative arguments as failure strategy. It relies on the assumption that matchers return complete results. Each possible pair of ontology entities which is not returned by the matcher is considered to be at risk, and a negative argument is generated (h = -).

The values v in V correspond to the different matching approaches and each matcher m has a preference ordering m over V such that its preferred values are those it associates to its arguments. For instance, consider V= {l, s, w}, i.e., lexical, structural and wordnet-based approaches, respectively, and three matchers m l , m s and m w , using such approaches. The matcher m l has as preference order l m l s m l w. The basic idea is to obtain a consensus between different matchers, represented by different preferences between values. Arguments interact based on the notion of attack presented in §3.1.

The argumentation process can be described as follows. First, each matcher generates its set of correspondences, using some specific approach and then the set of corresponding arguments is generated. Next, the matchers exchange with each others their set of arguments -the dialogue between them consists of the exchange of individual arguments. When all matchers have received the set of arguments of each others, they instantiate their SVAFs in order to generate their set of acceptable correspondences. The consensual alignment contains the correspondences represented as arguments that appear in every set of acceptable arguments, for every specific audience (objectively acceptable).

In order to illustrate this process, consider two matchers, m l (lexical) and m s (structural), trying to reach a consensus on the alignment between the ontologies in Figure 1. m l uses an edit distance measure to compute the similarity between labels of concepts and properties of the ontologies, while m s is based on the comparison of the direct super-classes of the classes or classes of properties. Table 4 shows the correspondences and arguments generated by each matcher. The matchers generate complete alignments, i.e., if a correspondence is not found, an argument with value of h =is created. It includes correspondences that are not relevant to the task at hand. For the sake of brevity, we show only the arguments with h = + and the corresponding counter-arguments (Table 5). We consider 0.5 as the confidence level c for negative arguments (h = -). Considering V = {l, v}, m l associates to its arguments the value l, while m s generates arguments with value s. m l has as preference ordering: l ≻ m l s, while m s has the preference: s ≻ ms l. Having their arguments A, the matchers exchange them. m l sends to m s its set of arguments A l and vice-versa. Next, based on the attack notion, each matcher m i generates its attack relation ⋉ i and then instantiates its SV AF s i . The arguments A, D, E, G, H and J are acceptable in both SVAFs (they are not attacked by counter-arguments with h = -). F , I, and B (h = +) successfully attack their counter-arguments (h = -) L, M and N , respectively, because they have high-

Weaknesses and Challenges

As discussed above, argumentation for alignment agreement has been exploited in different ways, for different scenarios. However, there are still various challenges ahead for achieving a fully satisfying approach. We briefly consider some of them.

Confidence of arguments

In [START_REF] Trojahn | A cooperative approach for composite ontology mapping[END_REF], the notion of attack between the arguments highly depends on the confidence associated to the correspondences. Such confidence levels are usually derived from similarity assessments made during the matching process, e.g., from edit distance measure between labels, or overlap measure between instance sets. However, there is no objective theory nor even informal guidelines for determining such confidence levels. Using them to compare results from different matchers is therefore questionable especially because of potential scale mismatches. For example, a same strength of 0.8 may not correspond to the same level of confidence for two different matchers.

Complete alignments

Generating complete alignments is at first sight quite unrealistic, but it can nevertheless be supported by the observation that most matchers try to provide as much correspondences as possible. However, dealing with a large number of arguments can become prohibitively costly. Following the approach from [START_REF] Doran | Efficient argumentation over ontology correspondences[END_REF], the search space within the argumentation process can be reduced, by isolating only the correspondences that are relevant to the communication. Other authors isolate the subpart of the ontologies to be matcher relevant for the communication before matching only these pieces of ontologies instead of the whole ontologies [START_REF] Packer | Evolving ontological knowledge bases through agent collaboration[END_REF]. These approaches have to be developed with guarantees that the isolated items are the relevant ones.

Inconsistent alignments

An important issue in such argumentation for alignment agreement is related to the potential inconsistency in the agreed alignment. Indeed, even if the initial alignments are consistent, selected sets of correspondences may generate concepts that are not satisfiable.

Solving the inconsistency problem in alignments has two possible alternatives:

• express the inconsistency within the argumentation framework [START_REF] Amgoud | Bridging the gap between abstract argumentation systems and logic[END_REF];

• deal alternatively with the logical and argumentative part of the problem.

Integrating the logics within the argumentation framework seems a more elegant solution and it can be achieved straightforwardly when correspondences are arguments and incompatible correspondences can mutually attack each others. However, this works only when two correspondences are incompatible. When the set of incompatible correspondences is larger, the encoding is not so straightforward and may lead to the generation of an exponential amount of argument and attack relations. On the other side, alternating logical and argumentative treatments may also lead to prohibitive computational costs. In this case, the solution seems to be a trade-off between the computational costs and the expected consistency.

Availability of justifications

The presented approaches argue for or against a correspondence based on justifications for the arguments. They are thus highly dependent on justifications for the arguments provided with the alignments. Although, alignment servers provide the necessary metadata for storing such justification with alignments (see §2.1), it is not common for people or for matchers to provide this information. Ideally, matchers should provide such justifications, as a way to understand why a particular alignment is found or why a certain match is ranked higher than another. However, this is not common practice.

The development of such methods may therefore be slowed by the unavailability of justification metadata. It seems necessary to provide incentive to both automatic and manual matchers to generate this information. One such incentive could be, of course the ability to be involved in an argumentation process and then to provide better alignments. Another incentive would be to better help explain matcher results to users [START_REF] Shvaiko | Web explanations for semantic heterogeneity discovery[END_REF].

Other Related Work

This chapter has covered all the work carried out in the domain of alignment argumentation per se. However, in order to find alignments between ontologies used by agents, some work have proposed different techniques that we consider here. [START_REF] Silva | An approach to ontology mapping negotiation[END_REF] has proposed alignment negotiation to establish a consensus between different agents using the MAFRA alignment framework [START_REF] Maedche | MAFRA -a MApping FRAmework for distributed ontologies[END_REF]. The approach is based on utility functions used to evaluate the confidence in a particular correspondence in the context of each agent. These confidence values are combined in order to decide if the correspondence is accepted, rejected or need to be negotiated. A meta-utility function is also applied to evaluate if the effort necessary to negotiate is beneficial or not; it may so automatically change the thresholds so that some correspondences are directly rejected or accepted. The approach is highly dependent on the MAFRA framework and cannot be directly applied to other environments.

Schemes for obtaining ontology alignments through the working cycles of agents have been developed. They either observe failure or success of the communication and statistically learn the alignments [START_REF] Besana | How service choreography statistics reduce the ontology mapping problem[END_REF] or they use the interaction protocol of each agent for reducing the possible meaning of concepts used as performative [START_REF] Atencia | Semantic alignment in the context of agent interaction[END_REF]. [START_REF] Van Diggelen | ANEMONE: An effective minimal ontology negotiation environment[END_REF] presents an approach for agents to agree on a common ontology in a decentralised way. The approach assumes that each agent adopts a private ontology and shares an intermediate ontology. The private ontology is used for storing and reasoning with operational knowledge, i.e., knowledge relevant to a particular problem or task at hand. The intermediate ontology is used for communication. Communication proceeds by translating from the speaker's private ontology to the intermediate ontology which the hearer translates back again into its own private ontology. The authors show how to establish such an intermediate ontology, which is the common goal for every agent in the system. In the approaches we have presented, on the other hand, the result of the negotiation is a set of correspondences between the terms of the different ontologies.

[5] presents an ontology negotiation protocol to provide semantic interoperability in multi-agent systems in an automated fashion at run-time. The ontology negotiation protocol enables agents to discover ontology conflicts or unknown terms. Then, it goes through (i) incremental interpretations of the unknown terms with the help of external resources, (ii) clarification, by proposing putative correspondences, (iii) evaluation, through the impact of such correspondences on some tasks, and (iv) update of the ontology with the correspondence. The final result of this process is that each agent will converge on a single, shared ontology. In contrast, in the approaches presented in this chapter, agents keep their own ontologies that they have been designed to reason with, whilst generating alignments with other agent's ontologies.

In [START_REF] Morge | A formal framework for inter-agents dialogue to reach an agreement about a representation[END_REF], the authors propose an argumentation framework for inter-agent dialogue to reach an agreement on terminology, which formalizes a debate in which the divergent representations (expressed in description logic) are discussed. The proposed framework is stated as being able to manage conflicts between claims, with different relevancies for different audiences, in order to compute their acceptance. However, no detail is given about how agents will generate such claims. [START_REF] Trojahn | Using cooperative agent negotiation for ontology mapping[END_REF] proposes a cooperative negotiation model, where agents apply individual matching algorithms and negotiate on a final alignment. Basically, the negotiation process involves the exchange of proposal and counter-proposals that represents correspondences. Each correspondence is negotiated individually. Three kinds of agents interact, lexical, structural, and semantic, and the communication is managed by a mediator agent.

Final Remarks

This chapter has presented an overview of the approaches for alignment agreement based on argumentation. Such approaches provide a way for agents, with different ontologies, to agree upon mutually acceptable ontology alignments to facilitate communication within a dynamic environment.

We have discussed how two agents commiting to different ontologies can align their ontologies in order to interoperate and how agents relying on different matching approaches can agree on a common alignment. The approaches for both scenarios are not fully satisfying and there are still various challenges ahead for achieving such maturity.

Fig. 1

 1 Fig. 1 Fragments of ontologies o and o ′ with alignment A.

  nary relation on A. a ⋉ b means that the argument a attacks the argument b. A set of arguments S attacks an argument b iff b is attacked by an argument in S.

  In a VVAF A, ⋉, S, V, v, , s , an argument a ∈ A successfully attacks (or defeats) an argument b ∈ A (noted a †b) iff a⋉b∧(|{x|S(x, a)}| > |{y|S(y, b)}|∨|{x|S(x, a)}| = |{y|S(y, b)}|∧v(a) v(b)).

4. 1

 1 Argumentation over alignments for communication in multi-agent systems 4.1.1 Meaning-based argumentation Laera et al. proposed the meaning-based argumentation approach

Fig. 3 Fig. 4

 34 Fig. 3 Conjunctive queries.

Figure 4 . 1 .

 41 Figure 4.1.2 shows an AUML3 interaction diagram with the messages exchanged between the agents b and s during the negotiation of the price of the camera. The agents use the queries to search for correspondences between the messages sent from each other and the entities in the corresponding ontologies. In the example, the agent b sends a message to the agent s, using its vocabulary. Then, the agent s converts the message, using the DL queries.

id correspondence argument matcher A c l, 1 =

 1 zoom o , zoom o ′ , ≡, 1.0 c l,1 , l, 1.0, + m l B c l,2 = Battery o , Battery o ′ , ≡, 1.0 c l,2 , l, 1.0+ m l C c l,3 = M emoryCard o M emory o ′ , ≡, 0.33 c l,3 , l, 0.33, + m l D c l,4 = brand o , brandN ame o ′ , ≡, 0.22 c l,4 , l, 0.22, + m l E c l,5 = price o , price o ′ , ≡, 1.0 c l,5 , l, 1.0, + m l F c s,1 = CameraP hoto o , DigitalCamera o ′ , ≡, 1.0 c s,1 , s, 1.0, + m s G c s,2 = zoom o , zoom o ′ , ≡, 1.0 c s,2 , s, 1.0, + m s H c s,3 = brand o , brandN ame o ′ , ≡, 1.0 c s,3 , s, 1.0, + m s I c s,4 = resolution o , pixels o ′ , ≡, 1.0 c s,4 , s, 1.0, + m s J c s,5 = price o , price o ′ , ≡, 1.0 c s,5 , s, 1.0, + m s

  id correspondence counter-argument matcher L c l,6 = CameraP hoto o , DigitalCamera o ′ , ≡, 0.5 c l,6 , l, 0.5,m l M c l,7 = resolution o , pixels o ′ , ≡, 0.5 c l,7 , l, 0.5,m l N c s,6 = Battery o , Battery o ′ , ≡, 0.5 c s,6 , s, 0.5,m s O c s,7 = M emoryCard o , M emory o ′ , ≡, 0.5 c s,7 , s, 0.5,m s est confidence in their correspondences. C (h = +) is successfully attacked by its counter-argument O. The arguments in the preferred extension of both matchers m l and m s are: A, D, E, F , G, H, J, F , I, B and O. While resolution o , pixels o ′ , ≡, 1.0 , Battery o , Battery o ′ , ≡, 1.0 and CameraP hoto o , DigitalCamera o ′ , ≡, 1.0 have been accepted, M emoryCard o , M emory o ′ , ≡, 0.33 has been discarded.

Table 1

 1 Arguments and attacks.

	id argument	attack agent
	A

Table 4

 4 Correspondences and arguments generated by m l and m s .

Table 5

 5 Counter-arguments (attacks) for the arguments in Table4.

We describe here as VAF what[START_REF] Bench-Capon | Persuasion in practical argument using value-based argumentation frameworks[END_REF] calls an audience-specific value-based argumentation framework, but the result is equivalent.

The use of confidence profiles has since been explored to specify correspondence-type specific thresholds, resulting in the agreement over a greater diversity of agreed correspondences, and consequently more inclusive alignments[START_REF] Doran | Deciding agent orientation on ontology mappings[END_REF].

AUML -Agent Unified Modelling Language[START_REF]FIPA: Modeling: Interaction diagrams[END_REF].


Oliver Deussen
email: oliver.deussen@uni-konstanz.de

Tobias Isenberg
email: tobias@isenberg.cc

Halftoning and Stippling

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

photograph. He created his pattern by engraving lines in glass and darkened them using asphalt. Two or more such line patterns were superimposed and worked as a filter for the input image that divided it into dots of varying size (see Figure 3.1).

Digital Halftoning

In digital halftoning, the screening process is implemented by representing the input image by electronically generated dots. Companies such as Linotype in the 1970s developed film recorders where the film was electronically illuminated dot by dot using precision optics. When fully digital printing was invented for laser printers, halftoning meant to convert grayscale images into black and white pixels, that were directly realized by printers.

Threshold Quantization

The easiest way to convert a given grayscale image into black and white pixels is to use a threshold, typically half of the highest intensity. Doing so, the resulting image shows large black and white areas (cf. Figure 3.2(a)). A random variation of the threshold avoids such large areas but introduces noise (Figure 3.2(b)).

Each decision if a pixel is represented in white or in black introduces a visual error. If the threshold is randomly varied, this error statistically averages and the overall image appears in the right tonal values. However, the noise remains and thus better techniques were developed.

Floyd and Steinberg [START_REF] Floyd | An Adaptive Algorithm for Spatial Grey Scale[END_REF] invented error diffusion for halftoning. When representing a pixel in white or black, the error in grayscale is determined and diffused to the neighbor pixels. The simplest case is one-dimensional (cf. Algorithm 3.1), here a line of pixels is processed left to right and the error is diffused to the right neighbor.

In Here four pixels around the current pixel are updated. The error is distributed with individual weights that were found by experiments. on the input image. Since the threshold values repeat regularly, the image impression is also more regular than with error diffusion.

Stippling

Stippling is an illustration technique that relies on dots. In contrast to halftoning methods, dots are distributed manually. The artists tries to set dots randomly but in most cases with almost uniform point-to-point distances.

The technique allows artists to represent tone plus material of an object, thus such techniques are used by scientific illustrators when objects have to be printed in black and white while faithfully representing their surface details. An example from biology is shown in Figure 3.4, the surface of a bone is represented by the smooth arrangements of the dots, especially in the lighter areas almost uniform point-topoint distances are visible.

While in Figure 3.4 silhouette lines were also used, in the following we want to concentrate on how to distribute points with the necessary characteristics by means of computers.

So called Centroidal Voronoi Tessellations create dot distributions that arrange points in the desired manner. Du et al. [START_REF] Du | Centroidal Voronoi Tessellations[END_REF] describe them thoroughly, an analysis of different configurations of such tessellations and corresponding energy levels are given in [START_REF] Gersho | Asymptotically Optimal Block Quantization[END_REF][START_REF] Newman | The Hexagon Theorem[END_REF].

Centroidal Voronoi Tessellations for creating stipple patterns were introduced in [START_REF] Deussen | Floating Points: A Method for Computing Stipple Drawings[END_REF][START_REF] Secord | Weighted Voronoi Stippling[END_REF]. Other applications for such point sets are sampling [START_REF] Kopf | Recursive Wang Tiles for Real-Time Blue Noise[END_REF] and numerical integration [START_REF] Smith | Recent Developments in Numerical Integration[END_REF][START_REF] Stoer | Introduction to Numerical Analysis[END_REF]. In both cases the spectral characteristics of such sets (Blue Noise characteristics) are the reason for their usage.

Voronoi Tessellations and Lloyd Relaxation

Let us assume that we have n points S = s 1 , .., s n on our paper. The Voronoi cell V (s i ) of a point is the area around s i for which each additional point on the paper would be closer to s i than to any other point of the given set S. The regions of all points in S form a tessellation of the plane, meaning that they are pairwise distinct and jointly covering the entire plane.

Such tessellations are called the Voronoi diagrams VD(S) of S. Since a tessellation of the entire plane would have open Voronoi regions for the outer points of S, typically such regions are closed by intersecting them with a (rectangular) frame that encloses the given point set. This frame is our canvas on which the points are distributed.

Ordinary Voronoi Tessellations use the Euclidean metric as a distance function. Many other distance functions can be used. However, for the purpose of Stippling the Euclidean distance is sufficient since it is a "natural" distance function with an intuitive relation between value and perceived distance.

Centroidal Voronoi Tessellations (CVTs) are ordinary Voronoi Tessellations with the additional property that every point s i is placed in the centroid c i of its Voronoi cell V (s i ). The centroid (xc i , yc i ) is defined by the moments of the area

m 0,0 i = y i2 y i1
x i2 (y)

x i1 (y) dxdy m 1,0 i = y i2 y i1
x i2 (y)

x i1 (y)
x dxdy

m 0,1 i = y i2 y i1 y x i2 (y) x i1 (
xc i = m 0,0 i m 1,0 i , yc i = m 0,0 i m 0,1 i (3.2)
with A i being the area of the Voronoi Cell and x i1 , x i2 , y i1 , y i2 the boundary of the cell. Such a Cendroidal Voronoi Tessellation is shown in Figure 3.5(b). The points are still almost at random but now with much less variance in their point to point distances.

Cendroidal Voronoi Tessellations can be achieved by applying the Lloyd relaxation to the points. This algorithm was invented by S.Lloyd in the 1960s at Bell Labs and later published in [START_REF] Lloyd | Least Squares Quantization in PCM[END_REF]. Each step of one iteration of this algorithm moves each point towards the centroid of its Voronoi region. If c i = (xc i , yc i ) is the centroid of a Voronoi Region the movement can be represented

s (t+1) i = s (t) i + α c (t) i -s (t) i , (3.3)
where α ∈ (0, 1] determines the speed of the movement. In the original algorithm α is set to one. The iteration is repeated until the movement of the points is below a given threshold. Figure 3.5(b) visualizes the movement during such a relaxation. The CVT minimizes the following energy function, which measures the compactness of the Voronoi Regions (see [START_REF] Du | Centroidal Voronoi Tessellations[END_REF]):

F v (S,V (S)) = n ∑ i=1 V (S i ) ||x -s i || 2 dx. (3.4)
This energy function sums up the integral of all quadratic distances of the points in a Voronoi Cell towards the corresponding point s i . This is minimal for compact regions with almost uniform aspect ratio, thereby approximating hexagons [START_REF] Du | Centroidal Voronoi Tessellations[END_REF]. Furthermore, it implies an almost uniform distribution of point-to-point distances since these distances are maximized for compact regions. The Lloyd relaxation minimizes Equation 3.4 and therefore can be used as a local optimization method for F. It moves the points into a distribution with almost uniform point-to-point distance. If continued for too long, it converges to a hexago- nal distribution. This is not desired and typically iterating is stopped after a smaller number of steps.

Weighted Voronoi Tessellations

The Lloyd iteration distributes points in a uniform manner. However, for representing an input image we need varying density and thus have to find ways to modify the sizes of the Voronoi cells locally. Secord [START_REF] Secord | Weighted Voronoi Stippling[END_REF] published a variant of the iteration in which every point on the plane is assigned a weight in proportion to the needed point density (grayscale value).

For doing so, the definition of the moments from Equation 3.1 is modified in order to encapsulate the weights:

m 0,0 i = y i2 y i1
x i2 (y)

x i1 (y) ρ(x, y)dxdy m 1,0 i = y i2 y i1
x i2 (y)

x i1 (y) xρ(x, y)dxdy m 0,1 i = y i2 y i1 y x i2 (y)
x i1 (y) ρ(x, y)dxdy (3.5)

with ρ(x, y) being the density function that reflects the needed point density on the image. Parts of the equations can be precomputed, see [START_REF] Secord | Weighted Voronoi Stippling[END_REF] for details, this allows for a fast computation of the integrals.

Let us have a look what can be produced with this simple optimization scheme. Since the method only moves points, an initial set has to be given. Usually one uses one of the above described halftoning methods and for every black pixel one dot is created. Move the mass centroids of the objects onto the mass centroids (xc i , yc i ) of the Voronoi cells 5. rotate the objects main axis so that it matches the main axis ϕ of V (o i ) end until the object positions converge

Beyond Stippling

In general, Lloyd's relaxation method can be applied to arbitrary objects, provided that their Voronoi Diagram can be calculated. For each object the center of gravity is determined. During iteration, the object is moved so that its center of gravity lies upon the center of gravity of its Voronoi Region. Additionally, objects can now be rotated (see Algorithm 3.3).

To compute the rotations we need to determine the second-order moments of the Voronoi cells:

m 1,1 i = y i2 y i1
x i2 (y)

x i1 (y) xydxdy m 2,0 i = y i2 y i1
x i2 (y)

x i1 (y)

x 2 dxdy m 0,2 i = y i2 y i1 y 2

x i2 (y)

x i1 (y)

dxdy (3.6)
Using these moments and mass centroids one is able to calculate the main inertia axes and the desired rotation angle ϕ for the object . The two-dimensional inertia tensor is given as

J = µ 2,0 µ 1,1 µ 1,1 µ 0,2
The eigenvalues of J form the maximal and the minimal inertia moments j 1 , j 2 :

j 1,2 = 1 2 (µ 2,0 + µ 0,2 ± (µ 2,0 -µ 0,2 ) 2 + 4µ 2 1,1 . (3.7)
The angle ϕ of the main inertia axis is the angle of the eigenvector v 1 of J which belongs to the eigenvalue j 1 : Figure 3.9 shows an object with its main axes (solid arrows), its Voronoi cell and its main axes (dashed arrows). These axes are determined for each iteration and the object is rotated so that the axes match.

This allows the user to set up the algorithm for the extension of Lloyd's relaxation that is able to incorporate object rotations. Within the process, it is assumed that first the mass centroid of the object is moved over the mass centroid of the corresponding Voronoi cell, and that the orientation is then adapted.

In Figure 3.10(a) a set of points and lines is shown. Applying the method an even distribution as shown in Figure 3.10(b) is achieved. Please note that the iteration works well with the very badly distributed initial set shown in Figure 3. 10(a).

The variants of the iteration can be mixed while working with an object set. Similar to what was proposed earlier [START_REF] Deussen | Floating Points: A Method for Computing Stipple Drawings[END_REF], an interactive editor was built that allows the user to model sets of objects in various ways. One can move objects, insert or delete them using a number of "brushes". A special variant of the editor allows the user to apply one or more steps of each variant of the iteration.

The editor also enables the user to generate mosaics [START_REF] Fritzsche | Interactive Design of Authentic Looking Mosaics using Voronoi Structures[END_REF] (for more detail see Chapter 10). Here, small tiles have to be arranged in order to follow important struc-

Stippling by Example

The techniques described so far create stipple patterns with a single characteristicdespite the fact that artists most often develop variants of such a patterns according to their own taste and style. It would, therefore, be desirable to create such stipple distribution patterns from examples given by the artists.

Such an approach was presented by Kim et al. [START_REF] Kim | Stippling By Example[END_REF]. For this work an example of a stipple drawing has to be given that incorporates different tonal values. In a first step patterns for a set of tonal values are extracted and their dot distribution is determined.

Since in hand-made stipple drawings the stipple marks have a variety of forms, such forms are extracted and stored together with the stipple distribution. A statistical analysis of the distribution [START_REF] Maciejewski | Measuring Stipple Aesthetics in Hand-Drawn and Computer-Generated Images[END_REF] is used to find parameters for the stipple synthesis done on the basis of a texture synthesis algorithm. Another approach of stippling by example by Martín et al. [START_REF] Martín | Example-Based Stippling using a Scale-Dependent Grayscale Process[END_REF][START_REF] Martín | Scale-Dependent and Example-Based Stippling[END_REF] does not look at the statistics of the stipple point distribution but, instead, at the resolution and scale at which the stipple dots are placed as well as the specific shape of the individual points. This technique addresses one of the limitations of the previous one by Kim et al. [START_REF] Kim | Stippling By Example[END_REF]-namely the inability of Kim et al.'s technique to produce the nice merging of stipple points in medium gray regions.

To address this issue, Martín et al. [START_REF] Martín | Example-Based Stippling using a Scale-Dependent Grayscale Process[END_REF][START_REF] Martín | Scale-Dependent and Example-Based Stippling[END_REF] no longer treat the stipple points as black dots on a white background. Instead, they use grayscale scans of actual stipple points which they distribute based on halftoning. However, they also compute the correct resolution of stipple points on a paper of a given size, and use stipple dot scans of the appropriate pixel size so that the resulting scale-dependent images are produced for a given paper size (e.g., A4 or Letter paper). Moreover, due to the grayscale treatment, the grayscale stipple dots overlap and thus create the merging effects known from hand-made stippling. Interestingly, the randomized halftoning distributions that result from this process exhibit similar statistics as hand-made stippling, confirmed using Maciejewski et al.'s [START_REF] Maciejewski | Measuring Stipple Aesthetics in Hand-Drawn and Computer-Generated Images[END_REF] distribution analysis.

Figure 3.14 shows an example of Martín et al.'s [START_REF] Martín | Example-Based Stippling using a Scale-Dependent Grayscale Process[END_REF][START_REF] Martín | Scale-Dependent and Example-Based Stippling[END_REF] technique. Based on the input image in Figure 3.14(a), a grayscale stipple image was produced at 600 ppi for A5 size (Figure 3.14(b)), and the same stipple distribution was generated for the 1200 dpi black-and-white image in Figure 3.14(c). Notice that due to the scaledependence the same stipple dot scans and the same distribution is used for both images because they were produced for the same paper size-even though they have a different (pixel) resolution.

Structure-Aware Stippling

One issue raised, among others, also by Martín et al. [START_REF] Martín | Example-Based Stippling using a Scale-Dependent Grayscale Process[END_REF][START_REF] Martín | Scale-Dependent and Example-Based Stippling[END_REF] is that low-level stipple placement is not sufficient for being able to produce high-quality illustrations. While Martín et al. analyze the stipple process by traditional stipple artist including such high-level processing, some authors have tried to incorporate higher-level processing into the NPR stippling pipeline (also compare some of the hatching techniques described in Chapter 4). For example, Mould [START_REF] Mould | Stipple Placement using Distance in a Weighted Graph[END_REF] transforms the input image into a regular graph whose edges are weighted according to the local gradient magnitude. Then, Mould uses a version of Disjkstra's algorithm to place stipple dots based on the graph. Next, Mould places the dots progressively along the frontiers of growing regions, which preserves the structure of meaningful artifacts such as edges in the images.

A related technique by Kim et al. [START_REF] Kim | Feature-guided Image Stippling[END_REF] attempts to re-create the traditional hedcut illustration style which arranges stipples dots along lines for portraits of people. They first extract a line map and a tone map of the input image, then build a distance field and from that offset lines, and then use the extracted maps to optimize the placement of stipple dots. A different group of authors, Kim et al. [START_REF] Kim | Automated Hedcut Illustration using Isophotes[END_REF], extend the initial portrait stipple approach by adding perceptual depth cues to the stipple image. Kim et al. [START_REF] Kim | Automated Hedcut Illustration using Isophotes[END_REF] extract the image edges as well as a number of isophote lines (i.e., lines of the same brightness) and use these, similar to Kim et al. [START_REF] Kim | Feature-guided Image Stippling[END_REF], as means to place stipple points. The isophote lines are extracted by quantizing the input image and extracting edges of identical color value. Based on the edge map and the isophote map, Kim et al. then produce a weighted distance map which they use to produce offset lines which, in turn, are used to place stipple points.

Recently, Li and Mould [START_REF] Li | Structure-Preserving Stippling by Priority-Based Error Diffusion[END_REF] suggested another way for stipple rendering to take the input image's structure into account using structure-aware error distribution that also permits the user to control how many stipple points are being used. For this purpose, Li and Mould consider one pixel to be one stipple and provide means to reduce the number of stipples by increasing the positive and reducing the negative errors to avoid having to place too many stipples (on a regular grid). Both types of error result in less pixels and, thus, less stipples being placed. This approach results in a high degree of preservation of the structure in the input image, even if only relatively few stipple dots are being used to represent the input image. Moreover, Li and Mould [START_REF] Li | Structure-Preserving Stippling by Priority-Based Error Diffusion[END_REF] also describe a number of further adjustments that result in different effects such as screening using textures or patterns.

Conclusion

Stippling is a powerful but cumbersome illustration technique for scientific illustrators since it allows to represent grayscale values and texture at the same time. It is widely used in archeology and biology. Computer-generated stipple drawings allow the production of such illustrations, for example for scientific visualization purposes, much faster since automatic methods exist that mimic what artists do.

Data-driven methods use patterns created by artists. They enable to capture the style of an illustrator quite precisely. Such methods enable the computer to create a much larger variety of patterns with different spatial characteristics; however, the price is that we have to use much more complex methods.

Fig. 3 . 1

 31 Fig. 3.1 Reproducing a photograph by multiple line patterns. (a) First line screen; (b) second line screen; (c) resulting screening pattern; (d) Input Image: Rosemary Ratcliff / FreeDigitalPhotos.net; (e) resulting halftoning pattern.

Fig. 3 .

 3 Fig. 3.2 (a) Quantization with fixed threshold; (b) threshold is varied randomly.

Figure 3 .

 3 3(a) the result of one-dimensional Floyd Steinberg quantization is shown. Vertical patterns appear since for every line almost the same error is distributed leading to almost the same patterns in every line. The two-dimensional variant of the algorithm (see Algorithm 3.2) avoids such patterns since here the er-Algorithm 3.1 One-dimensional Error Diffusion Input: A grayscale image Output: An image of black and white pixels approximating the input for y := height to 0 step 1 { for x := 0 to width-1 step 1 { if (input[x, y] > 127) K := 255; else K := 0; error := input[x,y] -K; input[x+1, y] := input[x+1, y] + error; } } ror is not just distributed to the right neighbor but to the local neighborhood of the pixel.

Fig. 3 . 3 Algorithm 3 . 2

 3332 Fig. 3.3 Floyd Steinberg quantization: a) in the one-dimensional version vertical patterns appear; b) the two-dimensional variant avoids this.

Fig. 3 . 4

 34 Fig. 3.4 Manually generated stipple drawing. Image courtesy by Brian L. Sidlauskas, Oregon State University.

Fig. 3 . 5

 35 Fig. 3.5 (a) Voronoi Diagram; (b) Movement of points during relaxation.

Fig. 3 .

 3 Fig. 3.6 (a) Initial Point distribution for a face; (b) Point distribution after 20 steps of Lloyd's relaxation. The points spread over the entire drawing plane, image details are lost.

Fig. 3 . 7

 37 Fig. 3.7 (a) Point distribution in weighted Voronoi Tessellation; (b) Point distribution with points in white regions omitted.

Fig. 3 . 8

 38 Fig. 3.8 Automatically stipple illustration of the bone from Figure 3.4.

Figure 3 .

 3 Figure 3.6(a) shows such an initial point distribution for the face of a woman. If we apply the normal Lloyd Iteration for this point set, the points are spread over the entire drawing plane and all the details of the face are lost (cf.Figure 3.6(b)). In Figure 3.7(a) a weighted Centroidal Voronoi Tessellation is displayed. Here, in addition to the initial distribution the image itself was given to determine density and weights. Due to the weights the details of the face are captured better. If all points that are placed on white areas are removed the result looks similar to a stipple drawing (cf.Figure 3.7(b)).Finally, in Figure3.8 the automatically stippled version of the bone of Figure3.4 is shown. Please note that this result is entirely automatic and no additional lines are inserted.

  Figure 3.6(a) shows such an initial point distribution for the face of a woman. If we apply the normal Lloyd Iteration for this point set, the points are spread over the entire drawing plane and all the details of the face are lost (cf.Figure 3.6(b)). In Figure 3.7(a) a weighted Centroidal Voronoi Tessellation is displayed. Here, in addition to the initial distribution the image itself was given to determine density and weights. Due to the weights the details of the face are captured better. If all points that are placed on white areas are removed the result looks similar to a stipple drawing (cf.Figure 3.7(b)).Finally, in Figure3.8 the automatically stippled version of the bone of Figure3.4 is shown. Please note that this result is entirely automatic and no additional lines are inserted.

Figure 3 . 2 . 3 .

 323 Figure 3.6(a) shows such an initial point distribution for the face of a woman. If we apply the normal Lloyd Iteration for this point set, the points are spread over the entire drawing plane and all the details of the face are lost (cf.Figure 3.6(b)). In Figure 3.7(a) a weighted Centroidal Voronoi Tessellation is displayed. Here, in addition to the initial distribution the image itself was given to determine density and weights. Due to the weights the details of the face are captured better. If all points that are placed on white areas are removed the result looks similar to a stipple drawing (cf.Figure 3.7(b)).Finally, in Figure3.8 the automatically stippled version of the bone of Figure3.4 is shown. Please note that this result is entirely automatic and no additional lines are inserted.

Fig. 3 . 9 Fig. 3 .

 393 Fig. 3.9 Mapping the axes of the object (solid arrows) to the axes of the Voronoi cell (dashed arrows) defines the rotation of the object.

Fig. 3 .

 3 Fig. 3.11 A stipple illustration that uses different small objects as stipple marks. © Eurographics Association, used by permission.

Fig. 3 .

 3 Fig. 3.12 Computer-assisted mosaics using the modified Lloyd's relaxation. © Eurographics Association, used by permission.

  and 3.12.

Figure 3 .

 3 [START_REF] Martín | Example-Based Stippling using a Scale-Dependent Grayscale Process[END_REF] shows example results ofKim et al.'s [7] approach. The grayscale image in Figure3.13(a) and the artistic stipple distribution in Figure3.13(b) is given as input. The algorithm produces the new stipple drawing shown in Figure 3.13(c). In contrast to the standard solution using weighted Voronoi Stippling (see Figure 3.13(d)), the distribution of dots follows the characteristics of the input.

Fig. 3 .

 3 Fig. 3.13 Stippling by example: (a) grayscale image; (b) artistic stipple example used as the source of the example-based stipple distribution; (c) computer-generated pattern by example; (d) weighted Voronoi stippling for comparison. (a) copyright © David Darling, used by permission, (b) copyright © 2009 William M. Andrews, used by permission, (c) copyright © 2009 Kim et al., used by permission.

Fig. 3 .

 3 Fig. 3.14 Resolution-dependent stippling by example: (a) input image; (b) grayscale stipple result; and (c) black-and-white thresholded at a higher pixel resolution. (a) Copyright © 2012 Domingo Martín, used by permission; (b,c) copyright © 2012 Martín et al., used by permission.