Rakebul Hasan

Fabien Gandon

Explanation in the Semantic Web: a survey of the state of the art

Keywords: Explanation, justification, Semantic Web, trust Explication, justification, Web sémantique, confiance

Semantic Web applications use interconnected distributed data and inferential capabilities to compute their results. The users of Semantic Web applications might find it difficult to understand how a result is produced or how a new piece of information is derived in the process. Explanation enables users to understand the process of obtaining results. Explanation adds transparency to the process of obtaining results and enables user trust on the process. The concept of providing explanation has been first introduced in expert systems and later studied in different application areas. This paper provides a brief review of existing research on explanation in the Semantic Web.

Introduction

Semantic Web applications use interconnected distributed data and inferential capabilities to compute their results. A user might not be able to understand a Semantic Web application has solved a given query deriving new information and integrating information from across the Web, and therefore the user might not trust the result of that query. Semantic Web applications should provide explanations about how they obtain results in order to ensure their effectiveness and increase their user acceptance [START_REF] Mcguinness | Explaining answers from the semantic web: the inference web approach[END_REF]. Semantic Web applications should not only provide explanations about how the answers were obtained, they should also explain and allow users to follow the flows of information between them [START_REF] Mcguinness | Explaining semantic web applications[END_REF].

Expert systems were among the first software systems to include explanation facilities. Expert systems were intended to partially incorporate and augment human expertise in a well-defined, protocol oriented domain. The need for understanding why a system has failed to meet certain requirement has given rise to the need for explanation facilities. Expert systems were required not only to solve problems within a well-defined domain but also to impart an understanding of a given field by providing explanation of a given concept or entity. Expert systems without the explanation facilities became subject to credibility problems, especially in the safety critical domain and in the systems with rich intellectual contents. Explanation facilities were introduced in the expert systems with the intention of providing an understanding of why and how a particular conclusion has been reached. Overviews of explanation in expert systems can be found in [START_REF] Haynes | Explanation in Information Systems: A Design Rationale Approach[END_REF][START_REF] Moore | Explanation in expert systemss: A survey[END_REF][START_REF] Swartout | Explanations in knowledge systems: design for explainable expert systems[END_REF]. Explanation facilities in expert systems have evolved from reasoning trace oriented explanations, primarily useful for developers and knowledge engineers, to more user oriented interactive explanations justifying why a system behavior is correct, to casual explanations generated in a decoupled way from the line of reasoning. The realization of the explanation facilities in expert systems were motivated by enabling transparency in problem solving, imparting an understanding of why and how a conclusion has been reached, and hence enabling trust on the reasoning capabilities of the expert systems. These developments motivated adaptation and development of explanation facilities in other fields such as machine learning [START_REF] Glass | Explanation of Adaptive Systems[END_REF][START_REF] Stumpf | Toward harnessing user feedback for machine learning[END_REF], case-based reasoning [START_REF] Doyle | A review of explanation and explanation in casebased reasoning[END_REF][START_REF] Roth-Berghofer | Explanations and case-based reasoning: Foundational issues[END_REF], recommender systems [START_REF] Tintarev | A survey of explanations in recommender systems[END_REF], and Semantic Web.

In the this paper, we provide a review of the existing approaches to provide explanation in the Semantic Web. In section 3, we provide an overview of different approaches to represent the metadata which enable support for reasoning and provenance information. In section 4, we provide an overview of different approach for generation and presentation of explanation. In section 5, we focus our discussion on the important aspects of explanation approaches in the Semantic Web. In section 6, we conclude the paper.

Designing Explanation-Aware Semantic Web Applications

McGuinness et al. [START_REF] Mcguinness | Explaining semantic web applications[END_REF] investigate the Semantic Web application paradigms from an explanation perspective. Question answering on the Semantic Web, which is an interactive process involving human users and software agents, requires more processing steps than simple database retrieval. The paradigm shift introduced by the Semantic Web applications, from answering queries by retrieving explicitly stored information to using inferential capabilities, generates new requirements to ensure their effective use: "applications must provide explanation capabilities showing how results were obtained". Explanations improve users' understating of the process of obtaining results and add transparency to the process. Explanations make the results and process of obtaining results more credible. McGuinness et al. analyse the Semantic Web application paradigms in the context of explanations with the aim of identifying explanation requirements.

Characterization of Semantic Web Applications

McGuinness et al. characterize the important features of the Semantic Web applications from an explanation perspective:

Collaboration involves interaction and sharing of knowledge between agents that are dedicated to solve a particular problem. Semantic Wikis and applications developed via integration of Semantic Web services and multi-agent systems are examples of collaborative Semantic Web applications. Managing provenance, trust and reputation are the important issues form a collaboration perspective. Semantic Wikis, for example, enable storing project history and utilizing tools to perform intelligent queries on this history, and subsequently enable more transparent content management. Furthermore, in the reactive multi-agent systems, individual agents are often not autonomous and therefore the "intelligence" is a collective one which comes from interactions between agents. These heterogeneous and loosely-coupled agents or systems component must be able to discover new services by accessing service descriptions.

Autonomy of an individual agent can be seen as the ability to act independently. The degree of autonomy in traditional Web-based applications, such as search engines, is very little as they take input from users to achieve their goals. Semantic Web applications on the other hand have more autonomy. For example, a shopping agent can autonomously decide which services to call and compose, which content sources to use, how to enhance a query with background knowledge, to provide more useful and efficient answers to user's questions.

Use of ontologies provide support for heterogeneous and distributed data integration and allow dealing with inconsistencies of data from multiple sources in the

Explanation Criteria

Given these features of Semantic Web applications, McGuinness et al. identify criteria such as different types of explanations and consumption of explanation by humans or machine agents to analyze explanation requirements. The transitions logs of the manipulation steps which have been performed to derive results are known as justifications. These justifications enable provision of detailed explanation. Human understandable explanation generated from abstraction of these justifications is an important type of explanation providing details about what has been done to produce a conclusion. Provenance metadata enable providing another kind of explanation with details of information sources. Trust is another important subject in the context of explanation in the Semantic Web, especially, in distributed settings such as large online social networks. Representation, computation, combination, and presentation of trust present challenging research questions in this context. For machine consumption, explanations should be represented using standards in order to enable interoperability. Representation of justifications and provenance metadata in an interoperable way enables external software agents to make sense of explanation metadata. Human computer interface (HCI) issues such as the level of user expertise and the context of problem should be considered in the explanations that are aimed for human consumption. Visual explanations should be provided in a manageable way. Explanations should be presented with options for different degree of details such as summarized view and focused view allowing navigation between related information.

Explanation Requirements

Following the discussion of these explanation criteria, the authors discuss how these criteria relate to the Semantic Web application features discussed previously. From explanation and collaboration perspective, trust and reputation are important issues. If answers generated by Semantic Web applications are to be believed by users, the Semantic Web applications and agents will need to provide explanation of how the answers were obtained, especially, in cases where these Semantic Web agents and applications collaborate to generate complex results. In a distributed setting, users should be provided with explanation of the flow of information between the involved agents in the reasoning process. In addition, it is also important to provide explanation based on provenance metadata in this context. Explanation based on provenance will add transparency in the problem solving process by providing details about information sources used to obtain the answers. Explanation becomes even more important in applications with higher degree of autonomy. Autonomous agents should provide explanation on their complex process of obtaining results which might include complex logical inferences or statistical methods. Explanation plays an important role in applications with lower degree of autonomy as well. For example, in search engines, explanation facilitates improved query refinement by enabling users to better understand the process of obtaining search results. Ontologies play key role in the context of supporting and providing explanation. For example, ontologies can be effectively used to develop an interlingua to enable an interoperable explanation.

In [START_REF] Mcguinness | Explaining answers from the semantic web: the inference web approach[END_REF], McGuinness et al. present the following requirements for an infrastructure to enable applications to generate distributed and portable justifications, and subsequently presenting the justifications as user-friendly explanations for any produced answer: Support for knowledge provenance enables to establish user trust on background reasoners in question answering settings by enabling users to understand the source information of information used in the reasoning process. Knowledge provenance meta information may include source name, date and authors, authoritativeness of the source, degree of confidence, etc.

Support for reasoning information enables recording traces of information manipulation steps performed by the reasoners to obtain results. These reasoning traces may include meta-information about reasoners and actions performed by reasoners to derive answers, e.g. detailed trace of inference rules applied to obtain a conclusion. Support for explanation generation enables generation of human understandable explanations from reasoning traces and knowledge provenance. These knowledge provenance and reasoning traces are commonly known as justifications. Users may require explanation of what rules have been applied or how manipulation steps were performed to obtain a result. These user requirements about what kinds of explanation are required should be taken into account while recording justification meta-information.

Support for proof presentation enables presenting explanations in different forms, e.g. graphbased or textual presentation of the reasoning steps. Explanations should be presented with different degree of details taking into account the users' expertise and the context of problems.

Inria

We discuss these requirements in more details in 3 and 4.

2.4 Explanation-Aware Software Design (EASD) Principles

Forcher et al. present the explanation-aware system design (EASD) principles in [START_REF] Forcher | Explanation-aware system design of the semantic search engine koios[END_REF]. The EASD principles concern two key aspects, namely the development and the runtime of a system. The integration of explanation capabilities in a system during its development should not be too complicated and should not effect system performance and efficiency. The provided explanations should be understandable and sufficient for the users. Designing understandable explanation includes considering goals, preferences, knowledge of the system, and knowledge of the domain of users. Users should be provided with feedback mechanism to provide feedback about explanations to enable a dialog for a better understanding of explanations. A better understanding of explanation enables users to understand how and why a system reached a conclusion. This understanding enables transparency to the reasoning process of a system. An explanation of a reached conclusion should be a simplification of the actual process that the system went through to reach the conclusion. Explanations should have different kind of presentation such as natural language explanation, graphical explanation, or interactive explanation. In addition, there should be different kind of explanation such as concept explanation explaining a certain concept, and action explanation explaining the cause of a fact, action, or situation. The authors highlight that EASD does not intend to add explanation capability in the already developed systems.

Instead, EASD provides guidelines for the developers to integrate explanation capabilities during the development process. Concerning the runtime aspect, the system must be aware of the explanation scenarios and must be able provide explanation accordingly during its runtime. The authors consider three participants in any explanation scenario:

• Originator : the system or the agent that solves the problem.

• User : the addressee of the explanation.

• Explainer : the responsible for presentation, computation, and communication of explanation.

Different aspects of an explanation scenario such as the reactions of users upon receiving explanation, style of the explanation, and different types of user interaction play important role in different type of applications. These guidelines form the basis of EASD principle. Forcher et al. complement the EASD principles with an abstract architecture of a multilayered explanation model, shown in Figure 1. The tracing process constructs the trace model comprising of the information regarding the behavior of the originator. What goes in the trace model is predefined with respect to the explanation requirements of users. However, the process of formulating the information need results in extra construction overhead which should be kept to a minimum level. The selection process filters the required information and produces the selection model for providing explanation to users in a certain situation. The construction process produces the construction model by adding supporting information to the selection model or removing unrelated information from the selection model. The construction model contains the domain and context dependent information. The externalisation process transforms the construction model to the externalisation model containing a formal description for communicating explanations in various communication forms such as texts, charts, tables, etc. Finally, the presentation process applies the suitable layouts and styles to the externalisation model and transforms the externalisation model to the presentation model which is the final presentable explanation to end users. The mediation model contains the information about explanations such as why an explanation is provided in an explanation scenario, how the presentation and the content of the explanation correspond to each other.

Metadata for Explanation

McGuinness et al. [START_REF] Mcguinness | Explanation interfaces for the semantic web: Issues and models[END_REF] describe explanation in the context of Semantic Web as "Semantic Web metadata about how results were obtained". In the following subsections, we present the existing approaches to represent explanation metadata.

Proof Markup Language (PML)

According to McGuinness et al. [START_REF] Mcguinness | Explanation interfaces for the semantic web: Issues and models[END_REF], provenance information are important for a large number of users to believe the answers. Moreover, often provenance information (e.g. source of a particular piece of information) are the only information demanded by users as explanation. Therefore, provenance metadata concerning information sources such as how, when, and from whom any given piece of data is obtained are important aspects of explanation metadata. Another important aspect of explanation metadata is the information manipulation traces. In the Semantic Web applications, producing a result involves several information manipulation steps which can derive conclusions. The transaction logs of these information manipulation steps, namely the "traces", allow explaining how a result has been derived. The metadata representing the manipulation steps including conclusions, the information manipulation operations, and its antecedents are commonly known as justifications. These justifications facilitate rich explanation of how a conclusion has been drawn. Representing trust related information is another is another aspect of explanation metadata.

Proof Markup Language (PML) 1 [START_REF] Pinheiro Da Silva | A proof markup language for semantic web services[END_REF] is an interlingua to represent explanation metadata. PML consists of three OWL ontologies for representing provenance information, justification information, and trust information. Figure 2 shows the concepts of PML.

The PML provenance ontology (PML-P) provides primitives for annotating real world things. An instance of IdentifiedThings represents a real world thing and its properties allow annotating The PML justification ontology (PML-J) provides primitives for encoding justifications about derivation of a conclusion. A justification in PML-J is not limited to a logical reasoning step. A justification can be a step of a computation process, e.g. an information extraction step or a web service execution. A justification can also be a factual assertion or an assumption. An instance of NodeSet hosts a set of alternative justifications for a conclusion. The InferenceStep concept allows encoding additional justification related details such as a set of antecedent NodeSet instances, inference rules using the InferenceRule concept, and inference engines using the InferenceEngine concept.

The PML trust ontology (PML-T) provides primitives for representing trust assertions concerning sources and belief assertions concerning information. PML-T complements the established users' understanding by allowing explicit representation and sharing of trust related assertions.

Lightweight use of PML

The authors in [START_REF] Pinheiro Da Silva | Inference web in action: Lightweight use of the proof markup language[END_REF] introduce a restricted subset of PML constructs and tools for encoding very basic justifications and performing tasks such as retrieval and browsing of provenance information. The authors present strategies to simplify encoding in PML. The authors present three simplification assumptions. Simplification Assumption 1 is about not using alternative justifications so that each PML NodeSet has a single InferenceStep. The Simplification Assumption 2 is about not encoding any knowledge about the inference mechanism itself i.e. the the rules used to transform information in each steps of a given information manipulation process. The Simplification Assumption 3 is about not encoding any knowledge about how information have been asserted form a given source i.e. not encoding the processes and services used behind. The authors provide an evaluation presenting a user study to verify whether provenance plays a role for scientists to correctly identify and explain quality of maps. Although the evaluation is not exactly about the lightweight encoding of PML, the authors claim that the results of the evaluation are significant for lightweight encoding of PML as the provenance information used in the study was encoded considering the recommendations for lightweight use of PML.

AIR Justification Ontology (AIRJ)

AIR (Accountability In RDF) [START_REF] Kagal | Gasping for air-why we need linked rules and justifications on the semantic web[END_REF] is a Semantic Web-based rule language focusing on generating and tracking explanation for inferences and actions. AIR provides features such as coping with logical inconsistencies by allowing isolation of reasoning results which can cause inconsistencies in global state; scoped contextualized reasoning; and capturing and tracking provenance information such as deduction traces, or justifications. AIR provides two independent ontologies. One ontology allows the specification of AIR rules and the other one allows describing justifications. Figure 3 shows the concepts of the AIR justification ontology. The prefixes pmll, pmlp, pmlj, air in Figure 3 are namesapce prefixes for PML-Lite, PML-P, PML-J, AIR rule ontology respectively.

The reasoning steps of the AIR reasoner are considered as events and modeled as subclasses of pmll:Event. These different events are represented as BuiltinAssertion, BuiltinExtraction, Clos-ingTheWorld, ClosureComputation, Dereference, Extraction, and RuleApplication. Rules are considered as operations. air:Rule represents rules and it is defined as a subclass of pmll:Operation.

The ontology also provides properties to enable representing variable mappings in the performed operations.

Generation and Presentation of Explanation

As discussed in explanation requirements, what types of explanations are generated and how they are presented to users are important criteria for success of explanation-aware systems. In this section, we discuss how the existing the Semantic Web systems generate explanations, what they explain, and how these explanations are presented.

Inference Web

Inference Web [START_REF] Mcguinness | Explanation interfaces for the semantic web: Issues and models[END_REF][START_REF] Mcguinness | Explaining semantic web applications[END_REF][START_REF] Mcguinness | Explaining answers from the semantic web: the inference web approach[END_REF] is an explanation infrastructure which addresses explanation requirements of web services discovery, policy engines, first order logic theorem provers, task execution, and text analytics. Information manipulation traces of these various kinds of systems are encoded using the Proof Markup Language (PML). These metadata in PML are also known as PML proofs. Inference Web provides a set of software tools and services for building, presenting, maintaining, and manipulating PML proofs.

Figure 4 shows the architecture of inference web infrastructure. IWBase provides an interconnected network of distribute repositories of explanation related meta information. IWBase provides a registry-based solution for publishing and accessing information. Content publishers can register metadata and other supporting information such as inference rules, and inference engines. IWBase provides services to populate PML proofs. IWBase exposes the populated metadata as PML documents and provides browsing interfaces to access them. These PML documents can be also accessed by resolving their URI references. Figure 5 shows the browsing interface of IWBase.

IWSearch searches for PML documents on the Web and maintains an inventory of these documents. Users can then search for PML documents using different search interfaces offered by IWSearch. Inference Web provides a browser called IWBrowser which can display PML proofs and explanations in number of different formats and styles. These rich presentations include a directed acyclic graph (DAG) view known as global view, a focused view enabling step-by-step navigation between related explanations, a filtered view to show selected parts of an explanation, an abstraction view which shows abstract views of explanations with different degrees of details, and finally a discourse view which allows follow-up questions. Figure 6 shows an example presentation by IWBrowser. It shows the abstraction view for a proof. The IWAbstractor component allows users to write abstraction patterns for PML proofs and matches these patters against Inria proofs to provide an abstract view. In figure 6 for instance, an abstract view with many fewer steps is shown in the left side than the original proof shown in the middle with blue outline. Inference Web provides a general trust infrastructure called IWTrust which provide explanation with trust related information and allows filtering out unreliable information. IWTrust includes representation of trust aspects and trust computation services. In addition, it provides a browser with trust view to render the trust annotation in an article. Figure 7 shows an example of trust view. Different fragments of an article are rendered in different colors depending on the trustworthiness of these fragments when a user clicks the trust tab in the browser. This allows users to have an understanding of trustworthiness of rendered information just by looking at an article.

OntoNova Question Answering

OntoNova [START_REF] Angele | Ontology-based query and answering in chemistry: Ontonova project halo[END_REF] is an ontology-based question answering system in chemistry domain. OntoNova provides explanation in natural language along with its answers. OntoNova generates answer justifications with meta-inferencing. OntoNova inference engine produce log files representing the proof tree for a given answer. Such a file is given as an input to a second meta-inference step. This second meta-inference step explains the proof tree in natural language describing how the answer was derived. OntoNova allows specifying meta-inference rules for the original rules for question answering. The two step method for providing explanation has advantage such as: (i) provision of additional information with explanations when proof trees do not contain enough information, (ii) filter explanation paths in case of redundancies for same results, (iii) provision of explanation with different degree of details, (iv) provision of personalized explanation for

WIQA Framework

The WIQA -Web Information Quality Assessment Framework [START_REF] Bizer | Quality-Driven Information Filtering in the Context of Web-Based Information Systems[END_REF] provides functionalities for quality-based information filtering. The WIQA framework allows to employ different policies for information filtering. These policies combine content-based, context-based, and rating-based quality assessment metrics. An information consumer's understanding of the employed quality assessment metrics is a major factor that influence whether the information consumer trust or distrust any quality assessment result. The WIQA framework provides detailed explanation of information filtering process with the aim of supporting information consumers in their trust decisions.

The WIQA framework is able to provide explanation of why information satisfies a given WIQA-PL policy. The WIQA framework provides explanations in natural language for human consumption and explanation in RDF for further processing by software applications. The explanation generation process contains two steps. First, WIQA generates the parts of explanations of why constrains expressed as graph patters are satisfied. These different parts of explanations are generated using a template mechanism. In the second step, these explanation parts are supplemented with additional explanations of why constrains expressed as extension functions are satisfied.

The structure and the content of explanations are defined by using a template mechanism. Figure 8 shows the policy "Only accept information from information providers who have received more positive than negative ratings." The graph pattern in lines 7-10 describes the constrains that Inria must be satisfied for this policy. The policy uses an extension function wiqa:MorePositiveRatings. The policy contains an explanation template in lines 5-6. The explanation template has a reference to the wiqa:MorePositiveRatings extension function for generating explanations related to this extension function. Figure 9 shows the explanation of why a triple matches the policy shown in figure 8. Line 13 of the explanation is generated by the explanation template and explains why the constrain expressed as graph pattern is satisfies. Lines 14-25 are generated by the extension function wiqa:MorePositiveRatings and explain its reasoning process.

In addition to the natural language-based explanations, WIQA provides RDF-based explanations. WIQA describes the explanation trees (parts and subparts of an explanation) using the Explanation (EXPL) Vocabulary3 . WIQA provides the feature of construct template to enable describing the contents of RDF explanations. A construct template is defined by CONSTRUCT EXPLANATION keywords and a set of triple patterns. The contents of an RDF explanation are generated by taking the matched triples of the set of triple patterns defined in the construct template for this RDF explanation. The RDF-based explanations can be used by other software applications to do further processing in their application-specific ways.

Proof Explanation Using Defeasible Logic

The authors in [START_REF] Antoniou | Proof explanation for the semantic web using defeasible logic[END_REF][START_REF] Bassiliades | Proof explanation in the dr-device system[END_REF] present a nonmonotonic rule system based on defeasible logic which is able to answer queries along with proof explanations. Defeasible logic enables reasoning with incomplete and inconsistent information. The traces of the underlying logic engine are transformed to defeasible logic proofs. The authors introduce an extension to the RuleML4 , a unifying family of Web rule languages, to enable formal representation of explanations using defeasible logic. The proofs generated from the traces are represented using this RuleML extension. Software agents can consume and verify these proofs. In addition, the authors present graphical user interfaces to visualize the proofs and interact with them. Finally, the authors present an agent interface to enable multi-agent systems to interact with their system.

Explanation of entailments in OWL ontologies

Horridge et al. present two fine-grained subclasses of justifications called laconic justifications and precise justifications [START_REF] Horridge | Laconic and precise justifications in owl[END_REF]. Laconic justifications are the justifications whose axioms do not Figure 9: Explanation of why a triple matches a policy.

Inria contain any superfluous parts. Precise justifications are derived from laconic justifications and each of whose axioms represents a minimal part of the justification. The authors also present an optimized algorithm to compute laconic justifications showing the feasibility of computing laconic justifications and precise justifications in practice. The authors provide a Protégé ontology editor5 plugin as a tool to compute these types of justifications 6 . This tool shows justificationbased explanations of entailments. Figure 10 shows examples of explanations. A user can select an entailment from the list of entailments shown in the left handside. The right handside shows the explanation for the selected entailment. Kotowski and Bry [START_REF] Kotowski | A perfect match for reasoning, explanation and reason maintenance: Owl 2 rl and semantic wikis[END_REF] argue that explanation complements the incremental development of knowledge bases in the frequently changing wiki environments. The authors present a semantic wiki called KiWi7 which takes a rule-based inconsistency tolerant reasoning approach that has the capability of explaining how a given piece of information was derived. The reasoning approach also allows knowledge base updates in an efficient way by using reason maintenance. The authors argue that providing explanation is important for supporting users' trust and facilitates determining main causes of inconsistencies. KiWi stores the justifications of all derivations and use them for explanation and reason maintenance. KiWi presents explanations as natural language explanations and as tree-based explanations. Figure 11 shows the textual explanation for a triple in KiWi. Figure 12 shows a part of interactive explanation tree. The number nodes are Figure 11: An example of textual explanation in KiWi.

the triple ids corresponding to the triples in KiWi. Support nodes represent justifications. A selected derivation path is highlighted in yellow. A textual explanation of a selected derivation is shown on the right side. Figure 12: An example of interactive explanation tree in KiWi.

KOIOS Semantic Search Engine

Forcher et al. [START_REF] Forcher | Explanation-aware system design of the semantic search engine koios[END_REF] describe the realization of EASD approach in a semantic search engine called KOIOS. The KOIOS semantic search engine enables keyword-based search on RDF data. The KOIOS search engine first computes a set of relevant SPARQL queries from a set of given keywords. Users then select the appropriate queries to query a triple store containing RDF data. The search results are provided with explanations about how they are computed. The explanations justify how keywords are mapped to concepts and how concepts are connected. In addition, the explanations interpret the performed queries in an understandable way. The authors introduce a set of ontologies to formally describe the content of explanations provided by KOIOS. The KOIOS Process Language (KPL) is used to describe the behavior of the originator. The Mathematical Graph Language (MGL) is used to realise the graph based view of the process model. Finally, another ontology called VGL is used for visualizing graph based information. In addition, KOIOS includes a set of rules to transform a certain model described in RDF. The trace model is described in RDF and transformed step-by-step to a presentation model using a set of rules to provide different views of explanation. Figure 13 representation of the query by clicking on any concept. KOIOS also provide justification-based explanation. Figure 14 shows an example of justification-based explanation in KOIOS explaining keyword to type mapping.

Explanation in AIR

The AIR reasoner annotates all the performed actions and dependencies between these actions. These annotations are recursively converted to AIR justifications. AIR provides a feature to enable explanation in natural language. Rule authors can specify a natural language description in a definition of rule itself. These natural language descriptions can contain variables. These variable values are replaced with the current value during the reasoning process. AIR also provide a feature to declaratively modify justifications. This allows the degree of details in AIR justifications to be selectively controlled. The authors of AIR suggest registering AIR with the Inference Web infrastructure in order to provide explanations from AIR justifications. This provides the possibility to use the Inference Web explanation toolkit for AIR justifications.

Discussion

The research we have reviewed exposes several dimensions of explanation in the context of the Semantic Web:

1. Infrastructure: With the increasing growth of sharing Semantic Web data as part of Linked Data [START_REF] Berners-Lee | Linked data. W3C Design Issues[END_REF] initiatives, it is important that data publishers can publish their data along with explanation related metadata with ease. Explanation infrastructures should be able to accommodate common data publishing principle. Semantic Web explanation infrastructures should also address heterogeneous and distributed nature of the Web. Inference Web intent to address these issues. For example, explanation metadata can be described in PML documents and resolved using the URIs of the documents. However, Inference Web provides a centralized solution for publishing and consuming explanation metadata. Explanation metadata should be registered in the Inference Web repository to use their facilities. Moreover, the published metadata using Inference Web facilities have compatibility issues with Linked Data principles. For instance, not all the resources in PML documents are identifiable by URIs as there are blank nodes in PML documents. Our ongoing work [START_REF] Hasan | Linking justifications in the collaborative semantic web applications[END_REF] on applying the Linked Data principles intent to address these issues. With regard to diversity of different representation, explanation metadata should be published promoting interoperability. The W3C PROV-DM data model [START_REF] Moreau | Prov-dm: The prov data model[END_REF] can be used as an interchange data model across different systems in this regard. Different systems can define their explanation metadata model as application-specific and domain-specific extensions of PROV-DM. Applications across the Web can then make sense of explanation metadata in a unified manner. Consumers of these explanation metadata can use explanation presentation and visualization tools according to their needs.

2. Target: Human users and software agents both are target of explanation in Semantic Web applications. In the existing approaches, human users are provided with natural language explanations or graphical explanations promoting easy comprehension. Unlike the expert systems which were used by knowledgeable users and domain experts, the users of Semantic The existing research discuss explanation of information manipulation steps, operations, and proof trees of derived results. Additional provenance information such as how, when, and who provenance is provided in Inference Web explanations for more context and enable better understanding. Semantic Web applications use distributed interconnected data in their reasoning process. Explaining the network of data used in the reasoning process might be useful for users. This would enable users to understand the flow of information used in the reasoning process and have a better understanding to the data integration process performed by the reasoner. Explanation with details of complex computation processes might always not be as useful for non-expert users as they are for expert users. Exposing problem solving methods in certain scenarios might result in security threat. The existing research does not discuss how explanations, which expose problem solving methods, influence security and confidentiality of Semantic Web systems.

Representation:

The reviewed vocabularies to represent explanation metadata for machine consumption allow to describe proof trees for answers, processes used to compute answers, different types of provenance information, model for how explanations should be presented to human users, and trust related information. Other important aspects of explanation vocabularies are granularity and existence of blank nodes in the data described using them. Table 1 presents a comparison of reviewed vocabularies taking these aspect into account. Proof trees encode logical deduction of conclusions. PML, PML-Lite, and AIRJ provide primitives to encode proof trees as justifications of answers. KOIOS and EXPL vocabularies do not provide primitives for encoding proof trees as they concern mainly describing computation process and structure of presentation information. Process description concerns describing the information manipulation steps or the algorithms that compute answers. All the reviewed vocabularies except EXPL allow describing processes used to compute answers. Provenance information provide additional context to explanation. PML allow describing how, when, and who provenance. PML-Lite allows one additional provenance, location provenance. AIRJ inherits PML-Lite provenance features. KOIOS and EXPL do not provide any primitive to describe provenance. With respect to granularity, RDF statements can be made at several level of granularity such as triple or graph. PML, PML-Lite, and AIRJ do not strictly define their granularity. PML pml:Information class instances can refer to a triple, a graph URI, or even to a textual representation of a logical formula. PML-Lite and AIRJ follow similar approach. For instance, pmll:outputdata property can point to a graph represented by a set of triples.

In [START_REF] Khandelwal | Pml based air justification[END_REF], the authors introduce new AIRJ properties such as airj:matchedgraph to specifically make statements about graphs. The authors of KOIOS vocabularies do not provide details about granularity [START_REF] Forcher | Explanation-aware system design of the semantic search engine koios[END_REF]. EXPL uses RDF reification primitives to provide a triple level fine grained granularity. Presentation model allows describing how and what should presented to the human users as explanation. KOIOS provide VGL vocabulary to describe visualization of explanation. EXPL allows describing the structure and contents of different parts of explanations that are presented to human users. PML, PML-Lite, and AIRJ do not provide any primitive to describe presentation of explanation. Declaratively specifying presentation model enables different types of user interface technologies to render explanation contents. One of the main motivation for providing explanation is user trust. Only PML allows describing trust related information. Explanation facilities should allow to describe, capture and processing over captured trust. As a Linked Data common practice, blank nodes are avoided while publishing data [START_REF] Heath | Linked Data: Evolving the Web into a Global Data Space[END_REF]. Blank nodes add additional complexities in data integration in a global dataspaces. It is not possible to make statements about blank nodes as they do not have identifiers. PML and AIRJ use RDF container concepts such as NodeSetList. RDF containers use blank nodes to connect a sequence of items [START_REF]Rdf semantics[END_REF]. This approach makes it difficult to publish the data described using PML and AIRJ as Linked Data. In our ongoing work in [START_REF] Hasan | Linking justifications in the collaborative semantic web applications[END_REF], we present the Ratio4TA vocabulary to represent justifications supporting graph level granularity. Graph level granularity gives a flexible control as a graph can contain a single triple or many triples. Our next step in Ratio4TA would be to define it as an extension of W3C PROV-DM to enable better interoperability.

5.

Presentation: Explanations are presented to human users as natural language or as graphical explanation in the reviewed approaches. Different kinds of graphical representation have been used to present proof tree, user query, or the steps performed by information manipulation algorithms. As discussed previously, users with different level of expertise should be considered for Semantic Web applications. How to present complex information manipulation processes to the end users in an understandable way and how much details is useful in the context of Semantic Web need to be researched more. The EASD approach discuss providing context dependent explanations. Existing approaches such as [START_REF] Costabello | Dc proposal: Prissma, towards mobile adaptive presentation of the web of data[END_REF] on context-aware data consumption can be also applied to address providing different types of explanation depending on different types of users. Presentation models can be declaratively defined and associated with different context related information such as different user profiles. Different user interface rendering methodologies can then be applied on the defined presentation models to provide the final explanation user interfaces.

6. Interaction: Explanations should be provided with navigation support to enable end users to discover more related information. Other interaction models such as follow up or feedback mechanisms might also be useful in certain contexts. Inference Web provides explanation with navigation and follow up support. How users can interact trust information based on explanation would be another interesting area to explore.

Trust:

The reviewed research lacks studies about understanding how explanations influ-Inria ence user trust in the context of Semantic Web. In contrast to the expert systems, Semantic Web applications have new dimensions such as openness and distributed. Furthermore, Semantic Web applications have much broader and diverse user base than expert systems. How these aspects of Semantic Web influence trust needs to be studied more. Explaining the reasoning process might not be enough in the context of Semantic Web. In the existing work, only Inference Web provides an infrastructure for trust which includes a vocabulary to describe trust related information. However, how users trust can be captured and processed for further trust assertions is not discussed. Another interesting area to explore would be how explanation approaches can be applied to explain trust itself. For instance, explanation can be provided about who have trusted a given resource or about trust rating calculations.

Conclusion

In this paper, we have presented an overview of the design principles of explanation-aware Semantic Web systems, what kind of explanation metadata these systems use to provide explanation and how they represent these metadata, and finally how explanation is generated and presented to end users. We have also discussed the important aspects of ongoing research relating to explanation in the context of Semantic Web.

Figure 1 :

 1 Figure 1: Explanation-Aware Software Design.

1

  http://tw.rpi.edu/portal/Proof_Markup_Language Inria

Figure 2 :

 2 Figure 2: PML concepts.

3. 1

 1 .2 PML-Lite PML-Lite 2 is an ongoing work with the aim of constructing a simple subset of the three modules of PML. PML-Lite takes an event based modeling approach. PML-Lite provides primitives to represent provenance of data flows and data manipulations. The Event class represents information manipulation and flow steps. The Event class is an equivalent class of the NodeSet class of PML-J. The Operation class represents a performed operation and it is an equivalent class of the InferenceRule class in PML-P. The input and output data are represented by the Data class. The Information class and the Document class of PML-P are defined as subclasses of Data. The Agent class of PML-Lite is directly defined as a subclass of Thing unlike PML-P where it is defined as a subclass of Source. The Agent class of PML-Lite represents the actor performing an operation. Finally, PML-Lite allows representing the place of a performed operation through its Location class

Figure 3 :

 3 Figure 3: AIR Justification Ontology: the concepts without any prefix are in the airj namespace.

Figure 4 :

 4 Figure 4: Inference Web Explanation Infrastructure.

Figure 5 :

 5 Figure 5: The browsing interface of IWBase.

Figure 6 :

 6 Figure 6: An example of abstraction view.

Figure 7 :

 7 Figure 7: An example of trust view.

Figure 8 :

 8 Figure 8: An example of WIQA-PL policy.

Figure 10 :

 10 Figure 10: An explanation based on laconic and precise justifications

Figure 13 :

 13 Figure 13: Graphical User Interface of KOIOS.

Figure 14 :

 14 Figure 14: Justification of keyword mapping.

Table 1 :

 1 Web applications can have different background, skill level, and knowledge level because of the open nature of the Web. Level of user expertise should be taken into account while providing explanation. The presentations of explanations can change according to level of user expertise or context of user scenario. User profiling approaches might be applied to provide explanations addressing this issue. With regard to software agents, explanations should be described using open standards such as OWL ontologies. As pointed out previously, explanations also should be published using common data publishing principles such as Linked Data to enable external software agents to easily consume them. Comparison of explanation vocabularies 3. What is explained:

	Inria

RR n°7974

Inria

http://tw.rpi.edu/web/project/TAMI/PML-Lite Inria

http://www4.wiwiss.fu-berlin.de/bizer/triqlp/

http://ruleml.org RR n°7974

http://protege.stanford.edu/

http://owl.cs.manchester.ac.uk/explanation/

http://www.kiwi-project.eu/ RR n°7974

route des Lucioles -BP 93 06902 Sophia Antipolis Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

Acknowledgments

The work presented in this paper is supported by the CONTINT programme of French National Agency for Research (ANR) under the Kolflow project (ANR-2010-CORD-021-02).


M M Bagher

C Soler

N Holzschuch

Accurate fitting of measured reflectances using a Shifted Gamma micro-facet distribution

Keywords: Descriptors (according to ACM CCS): / I.3.7 [Computer Graphics]: Three-Dimensional Graphics and Realism-Color, shading, shadowing, and texture

Lab error 100% 0% 100% 0% Figure 1: gold-metallic-paint material from the MERL database. Comparison between measured data (c) and Cook-Torrance BRDF using (b) Beckmann distribution or (d) SGD distribution. (a) and (e): difference measured in Lab color space between ground truth and (b) and (d) respectively.

Introduction

Photorealism in image synthesis depends strongly on the material representations we use. Measured BRDFs [START_REF] Matusik | A data-driven reflectance model[END_REF] provide a high degree of realism, but have storage issue (33 MB for a single isotropic material), making them harder to fit in a rendering pipeline. It is also difficult to use them with importance sampling, as they have no analytical definition. BRDF models such as Phong, Lafortune or Cook-Torrance are much more compact: 8-10 parameters are enough to model an isotropic material, and are easy to combine with importance sampling in Monte-Carlo integration. We would like to compute the parameters of a BRDF model so that it photo-realistically resembles a measured material. Ngan et al. [START_REF] Durand | Experimental analysis of BRDF models[END_REF] proved that diffuse and glossy materi-als are well approximated using single lobe Cook-Torrance or Lafortune BRDFs; the models are less accurate for specular materials such as metals, metallic paints or shiny plastics.

Adding more lobes to the BRDF model makes it more accurate, at the expense of the stability of the fitting process. 3 lobes are usually considered to be the limit for automatic fitting. Highly accurate fitting for all BRDFs, ranging from diffuse to highly specular, is still impractical. This paper presents accurate and robust fitting for any BRDF (including metals) with a single lobe (in addition to the diffuse component). We use the Cook-Torrance BRDF model but with a different micro-facet distribution. The Cook-Torrance BRDF [START_REF] Torrance | Theory for off-specular reflection from roughened surfaces[END_REF] simulates the micro geometry of a material as specular micro-facets and derives the BRDF mathematically from the probability distribution of micro-facets. Although it is typically used with the Beckmann distribution, the model can be used with many other distributions. Our study of measured BRDFs [START_REF] Matusik | A data-driven reflectance model[END_REF] shows that shiny materials do not follow the Beckmann distribution: micro-facets are more likely to be aligned with the surface normal, resulting in a sharper peak, consistent with the smooth appearance.

We introduce the SGD probability distribution function for micro-facets. This distribution provides a more accurate fitting for all measured materials, comparing to existing BRDF models, from highly shiny to diffuse. We use the Cook-Torrance BRDF with SGD distribution to approximate measured materials resulting in a compact and accurate representation. Since the SGD distribution approximates measured data very well, we were able to design a simpler fitting method. This method converges quickly (2.5 minutes on average) and it only uses two slices of the measured data to fit the unknown parameters. This paper is organized as follows: in the next section, we review previous work on BRDF models and measurements. Then we present the Cook-Torrance model and micro-facet distributions. In section 4, we describe the SGD probability distribution function, and in section 5 our fitting method. Section 6 presents our results and compares them with previous work. In section 7, we conclude and discuss potential avenues for future work.

Previous work

Analytical BRDF models provide a reasonably realistic reflectance behavior at a very low computational and memory cost [TS67, CT82, War92, LFTG97]. Among these, microfacet BRDF models assume that the surface geometry is made of specular micro-facets and the BRDF model depends on the facets' slope distribution.

In the Cook-Torrance BRDF model [START_REF] Torrance | Theory for off-specular reflection from roughened surfaces[END_REF][START_REF] Cook | A reflectance model for computer graphics[END_REF], the reflectance is decomposed into a distribution term, a shadowing term, accounting for self-masking of the microgeometry, and a Fresnel term. For isotropic materials, the shadowing term is derived from the micro-facet distribution, through a double indefinite integration [Smi67, Bro80, BBS02]. Oren and Nayar [START_REF] Oren | Generalization of lambert's reflectance model[END_REF] accounted for interreflections in the micro-geometry in addition to masking and shadowing. Ashikhmin et al. [START_REF] Ashikmin | A microfacetbased BRDF generator[END_REF] proposed a formulation of micro-facet models that includes reciprocity and energy conservation. this is often ignored. Schlick [Sch94] approximates the components of BRDF models with rational fractions for faster computations. His approximation of the Fresnel term is widely used today. Lazanyi et al. [START_REF] Lazányi | Fresnel term approximations for metals[END_REF] introduced a more accurate approximation of the Fresnel term.

Matusik et al. [START_REF] Matusik | A data-driven reflectance model[END_REF] measured reflectance properties for a large range of materials. We use their data-base for all our tests. Ngan et al. [START_REF] Durand | Experimental analysis of BRDF models[END_REF] examined how classical BRDF models such as Lafortune [START_REF] Lafortune | Non-linear approximation of reflectance functions[END_REF] and Ashikhmin-Shirley [START_REF] Ashikmin | A microfacetbased BRDF generator[END_REF] can be used to approximate measured reflectances. They showed that Cook-Torrance [START_REF] Cook | A reflectance model for computer graphics[END_REF] provide the best fits, and specular materials are poorly approximated with a single lobe; the quality of the fitting improves with multiple lobes, but the fitting process becomes unstable. A better fitting is recommended by global optimization with branching and bounding for multi-lobe cases [YSL11].

Ashikhmin and Premoze [START_REF] Ashikhmin | Distribution-based BRDFs[END_REF] computed the BRDF model directly from the data using back-scattering: if the input and output directions are equal, the entire BRDF model collapses into a 1D function, representing the micro-facet distribution. This function is read from the data and stored in a compact form. Wang

The Cook-Torrance reflectance model

The Cook-Torrance BRDF model [START_REF] Cook | A reflectance model for computer graphics[END_REF] assumes that surfaces are made of random specular micro-facets (see Figure 2). The surface normal m follows a probability distribution function D. The full BRDF is:

ρ(i, o) = ρ d π + ρ s π F(i • h)D(θ h )G(i, o) cos(θ i ) cos(θ o ) ( 1
)
where i is the incoming direction, o is the outgoing direction, h is the half-vector (h = i + o, normalized). θ i , θ o and θ h are the respective angles between these vectors and the surface normal n. ρ d and ρ s are the diffuse and specular coefficients, respectively (see notations on Figure 2).

D is the probability distribution function for micro-facet normals. G is the shadowing and masking coefficient, expressing the amount of light that is blocked by other microfacets before reaching the point (shadowing), or after reflection (masking). For isotropic materials, G is approximated by a product of one-dimensional functions:

G(i, o) ≈ G 1 (i)G 1 (o) and G 1 is computed from D through a double integra- tion [Smi67, Bro80, BBS02, WMLT07].
F is the Fresnel term, depending on the refraction index η of the material. It is usually close to constant at normal incidence, and increases to unity at grazing angles.

The normal probability density, D

Given a direction ω = (θ, φ) and an infinitesimal solid angle dω centered around this direction, the probability for the normal of a micro-facet to be inside the cone (ω, dω) is D(ω) (ω.n) dω.

In order to be physically plausible, D should follow several requirements: it should be positive, the projected area of the micro-facets in a direction should be equal to the projected area of the macro-surface and in particular, D(ω) (ω.n) dω = 1. D is usually expressed as:

D(θ) = χ [0, π 2 ] (θ) cos 4 θ P 22 tan 2 θ ( 2
)
where P 22 (x) is a positive function of the variable x ∈ [0, ∞) and χ [0, π 2 ] (θ) ensures sidedness: it is equal to 1 if θ < π 2 , and 0 otherwise. With this expression,

D(θ) cos θ dω = 1 2 P 22 (tan 2 θ) d(tan 2 θ) (3) Since D(θ) (ω.n) dω = 1, we have ∞ 0 P 22 (x) d x = 1/π.
We use this expression for importance sampling [WMLT07]: for a given incoming direction i, we first pick a random micro-facet normal m with probability D(θ m ) cos θ m , then compute the reflected direction o so that m is the half-vector. Finally, we compute the sampling weight as the BRDF divided by the probability, multiplied by the Jacobian of o:

w o = ρ(i, o) cos θ o D(θ m ) cos θ m ∂ω o ∂ω m
To pick m with the probability D(θ m ) cos θ m , we need the associated Cumulative Distribution Function F:

F(θ m , φ m ) = φ m 0 θ m 0 D(θ) cos θ dω = φ m 2 tan 2 θ m 0 P 22 (u) du Beckmann Exponential TR/GGX P 22 (x) 1 πα 2 e -x/α 2 1 2πα 2 e - √ x/α 2 α 2 π(α 2 +x) 2 Table 1: P 22 functions corresponding to classical micro- facet distributions, with x = tan 2 θ.
F is separable: F = F φ F θ , with F φ and F θ from 0 to 1:

F φ (φ m ) = φ m 2π (4) F θ (θ m ) = π tan 2 θ m 0 P 22 (u) du (5)
Assuming we have two uniform random variables u 1 and u 2 in [0, 1), we get the sampling equations:

φ m = F -1 φ (u 1 ) = 2πu 1 θ m = F -1
θ (u 2 ) For any micro-facet distribution D following Equation 2, importance sampling reduces to computing the integral of P 22 and inverting it.

Shadowing and masking

In early versions of the Cook-Torrance BRDF [TS67] the shadowing function G was independent from the microfacet distribution. Further research [Smi67, Bro80, BBS02] proved that we get a more accurate shadowing term by integration from the micro-facet distribution D. G is approximated as the product of two one-dimensional functions:

G(i, o) ≈ G 1 (θ i )G 1 (θ o ). G 1 is computed from D through a double integration: P 2 (r) = ∞ -∞ P 22 r 2 + q 2 dq (6) Λ(θ) = ∞ 1 tan θ (r tan θ v -1) P 2 (r) dr G 1 (θ) = χ [0, π 2 ] (θ) 1 + Λ(θ)
For further details, please refer to the original papers or the short summary in [WMLT07].

Existing distributions

Table 1 lists the P 22 functions corresponding to existing micro-facet distributions. Beckmann is frequently used [START_REF] Cook | A reflectance model for computer graphics[END_REF]; it is a Gaussian in tan θ, and is also very close to the Phong distribution [WMLT07]. The exponential distribution is mostly used for the propagation of radio waves [BBS02, Bro80], and has a sharper peak and larger tails than Beckmann. The Trowbridge-Reitz/GGX distribution [TR75, WMLT07] has a sharper peak and larger tails than Beckmann and Exponential distributions. It is hard to compare measured data with BRDF models, since models depend on position and several functions. For simple comparisons, we take i = o. As a consequence, h = i: we get an equation that only depends on θ h , with two unknown functions D and G 1 [START_REF] Ashikhmin | Distribution-based BRDFs[END_REF]:

ρ(θ h ) = ρ d π + ρ s π F(0)D(θ h )G 1 (θ h ) 2 cos 2 (θ h ) (7)
For small values of θ h and specular materials, G 1 is almost constant, equal to 1 (see Figure 5). The measured data varies only with D, and we can observe directly the micro-facet distribution.

Figure 3 compares the measured distribution D for brass from the MERL database [START_REF] Matusik | A data-driven reflectance model[END_REF] with approximations using different distributions. The peak of the measured distribution is much sharper than the predictions, while the tail is larger. If we fit the tail accurately (for example with the Beckmann distribution, α = 7×10 -2 ), then we miss the peak. On the other hand, if we fit the peak well, we miss the tail. To fit this data with existing distributions we would need several lobes. This observation holds for many materials in the MERL database: metals, metallic paints and shiny plastics.

At large angles, the measured distribution seem to decrease exponentially. But for small angles, the decrease is sharper than an exponential. Based on this observation, we suggest a slope in x -p , where x = tan 2 θ h and p is a parameter that depends on the model, multiplied by an exponential factor:

P 22 (x, α, p) = K α,p e -x α (x + α 2 ) p (8)
where K α,p is a normalization factor. With this distribution, we fit the measured data accurately (see Figure 3(b)), both at the peak and the tail.

The SGD distribution

We compute the normalization factor K α,p so that

∞ 0 P 22 (x) d x = 1/π.
The result is a shifted gamma distribution (SGD):

P 22 (x) = α p-1 Γ(1 -p, α) e -α 2 +x α α 2 + x p D(θ m ) = χ [0, π 2 ] (θ m ) π cos 4 θ m P 22 tan 2 θ m Γ is the incomplete Gamma function: Γ(s, x) = ∞ x t s-1 e -t dt
The SGD fits accurately a large range of materials, from diffuse to specular (see Figures 3(b), 4 and the supplemental material).

Shadowing and masking

Once we have D, we can compute the shadowing and masking function, G 1 , using Equation 6:

P 2 (r) = 1 √ παΓ(1 -p, α) U p, p + 1 2 , α + r 2 α e -α-r 2 α Λ(θ) = ∞ 1 tan θ (r tan θ -1) P 2 (r) dr G 1 (θ) = χ [0, π 2 ] (θ) 1 + Λ(θ)
where U is the confluent hyper-geometric function of the second kind. We do not have a closed form expression for G 1 . We either pre-compute G 1 using Gauss integration and store its values for varying θ or use the following approximation: Figure 5: The shadowing term G 1 is expensive for SGD. Our approximation is very accurate; the L 2 error is below 10 -5 . θ 0 ensures that G 1 (π/2) = 0. We get the (λ, c, k) parameters by fitting the approximation over the precomputed values, using Levenberg-Marquadt [Lou04]. This approximation is a very good fit for G 1 for all materials (the L 2 error is negligible, mostly below 10 -5 , see Figure 5). The choice between using stored values for G 1 and the approximation depends on the processing power, memory bandwidth and storage capacities. For offline rendering, where storage is not an issue, we use precomputed values. For GPU rendering, we use the approximation.

G 1 (θ) ≈      1 + λ 1 -e c(θ-θ 0 ) k if θ > θ 0 1 if θ ≤ θ 0 (9) θ 0 = π 2 -         log 1 + 1 λ c        

The Fresnel term

Since we have an expression for D and G 1 , we can express the Fresnel term using the measured data:

F(i • h) = m(i, o) - ρ d π π cos θ i cos θ o ρ s D(θ h )G 1 (θ i )G 1 (θ o ) (10)
where m(i, o) is the measured data. For simplicity, we will note θ d = arccos(i • h). Looking at the data for the Fresnel term, we make two important observations:

• The measured data behaves strangely at grazing angles.

In theory, the Fresnel term should be increasing with θ d up to 1 when θ d = π/2. The Fresnel term extracted from the measured data starts decreasing after a certain angle (from 70 o to 80 o ), and is equal to 0 for

θ d = π/2 (see Fig- ure 6(a)
). This is probably caused by the acquisition process: at grazing angles, the sensor is saturated by direct illumination from the light source † . We discard data for θ d > 70 o . • For some materials such as gold-paint or nickel, the Fresnel term does not behave as predicted by the Schlick approximation (see Figure 6(b)). Instead of a plateau followed by a sharp increase, we observe linear slope, followed by an increase. To model these materials, we suggest the following generalization of Schlick approximation:

F(θ d ) = F 0 + (1 -F 0 )(1 -cos θ d ) 5 -F 1 cos θ d ( 11
)
For F 1 = 0, we get the original approximation.

Importance sampling

Efficient Monte-Carlo integration requires importance sampling. For this, we need the inverse of the integral of P 22 (see Equation 5). We easily have F θ :

F θ = 1 - Γ 1 -p, α + tan 2 θ α Γ (1 -p, α)
but there is no closed form expression for the inverse for F θ , so we can't use it for exact importance sampling. As an approximation, we importance sample the GGX distribution [WMLT07], and compute weights, w, to fit our model: where u 1 and u 2 are realizations of a uniform random variable in [0, 1). Our BRDF model contains a diffuse and a specular component. We alternatively sample either component according to the following probabilities:

θ m = arctan α √ u 2 √ 1 -u 2 0
p specular = ρ s ρ d + ρ s p diffuse = 1 -p specular
The importance sampling weights for our distribution is:

w specular = 4 ρ s p specular F(i • h) D(θ h ) G(i, o) cos 3 θ m (α 2 + tan 2 θ) 2 α 2 w diffuse = ρ d p diffuse
This expression accounts for the jacobian of sampling m instead of o [WMLT07]. Figure 7 shows the same material rendered with and without importance sampling.

Fitting algorithm

Fitting RGB channels separately

Fitting BRDF models with measured materials is usually done in a two-step approach [START_REF] Durand | Experimental analysis of BRDF models[END_REF]: first compute the dif-fuse and specular colors using a linear least square optimization, then compute the BRDF parameters (α, F 0 ) through a second optimization. This approach places constraints on the second optimization process: the parameters must fit all RGB channels. We used a different approach: we compute the BRDF parameters separately for each channel, red, green and blue. Although we compute and store more data for each material, the fitting process is faster and more efficient, as we only fit real-valued functions, with less constraints for each fitting.

We also get wavelength dependent effects. The Fresnel term should change with the wavelength [START_REF] Lazányi | Fresnel term approximations for metals[END_REF] and we do find different values for F 0 and F 1 for the red, green and blue channels, for all materials in the MERL database (see supplemental material). Often, we get very similar values for the α and p parameters for the micro-facet distribution.

We do not take any explicit step to conserve the color of the material, since we treat each channel independently. We still get BRDF models that match very well the color of the measured materials (see Figures 1,8, and 10 and the supplemental). We attribute this to the very good match between our distribution function and the data behavior.

Non-linear optimization

Given the measured data for a single channel, we find the optimal value for the parameters (ρ d , ρ s , α, p, F 0 , F 1 ) so that the BRDF model is as close as possible to the measured data.

We could compute the L 2 norm of the difference between the BRDF model and the measured BRDF over the whole hemisphere, as in [START_REF] Durand | Experimental analysis of BRDF models[END_REF]. But regular sampling in θ i and θ o results in under-sampling near the specular peak, resulting in poor quality fits. Instead we fit in two steps: Each step is the fitting of a real-valued function of several parameters, which is simple and stable. Although we fit the parameters using only two slices of the measured reflectance, we still capture the full behavior of the BRDF.

We define the following quantities:

• m(i, o): the full measured reflectance, as extracted from the database, • m h (θ h ) = m(h, h): the slice of the BRDF corresponding to

θ d = 0, • m d (θ d ) = m(i, reflection(i)): the slice of the BRDF corre- sponding to θ h = 0.
In a first step, we fit m h (θ h ) with:

ρ h (θ h ) = ρ d π + F r π D(θ h )G 2 1 (θ h ) cos 2 (θ h )
The function ρ h depends on 4 parameters: ρ d , F r , α and p. Using Levenberg-Marquadt optimization [Lou04], we find the value of these parameters that minimizes the error function:

E 1 (ρ d , F r , α, p) = i w i (m h (θ h ) -ρ h (θ h )) 2 (12)
At the end of this step, we have the value for 3 parameters: ρ d , α and p. The last coefficient, F r is the product of ρ s and the Fresnel term for θ d = 0.

In the second step, we first extract the specular coefficient times the Fresnel term from m d (θ d ) using the values ρ d , α and p we just computed:

ρ s F D (θ d ) = m d (θ d ) - ρ d π π cos 2 (θ d ) D(0)G 2 1 (θ d )
We fit this function with our Fresnel term approximation (Equation 11), using Levenberg-Marquadt optimization. The data gives us ρ s F 0 and ρ s F 1 . Using F D (π/2) = 1, we get ρ s , F 0 and F 1 .

Results and Comparison

Visual comparison

Figures 8 and 10 shows a side-by-side comparison for aventurine and colonial-maple-223 between images rendered using the measured reflectance from the MERL database and several BRDF models: Lafortune and Cook-Torrance with the Beckmann, TR/GGX and SGD distributions. For each model, we show the difference with the reference image, measured in Lab space. We chose the Lab color space because it is perceptually uniform. Qualitatively, our BRDF model provides the best approximation to the measured data.

In the supplemental material, we provide a similar comparison for all 100 materials in the MERL database: reference image and Cook-Torrance BRDF with Beckmann and SGD distributions, along with differences in Lab space. For 13 materials in the database, we couldn't find the corresponding parameters in the supplemental of [NDM05], so we only provide the comparison between the measured material and our distribution. Visually, the Cook-Torrance BRDF with the SGD distribution looks very close to the measured reflectance.

BRDF Lobes comparison

Figures 8(j), 10(j) and 9, plot the BRDF lobes for aventurine, colonial-maple-223, hematite, black-obsidian, nickel, and black-oxidized-steel, with the Beckmann, GGX and SGD distributions compared to the measurements, for four incoming directions (10 • , 30 • , 50 • , and 70 • ).

The SGD distribution closely fits the measured data, while the Beckmann distribution either misses the tail by trying to fit the peak of the lobe, or vice-versa. This is particularly evident for black-obsidian where the Beckmann distribution underestimates the peak. In the hematite, aventurine, nickel, black-oxidized-steel, and colonial-maple-223 cases, which are ranging from highly-specular to glossy-specular and glossy-diffuse, the Beckmann distribution significantly overestimates the lobes. The GGX distribution performs better than Beckmann and SGD is very close to the actual shape of the lobes.

The supplemental material provides the same comparison for all 100 materials in the MERL database: lobes from the measured data and lobes from the Cook-Torrance BRDF, using Beckmann and SGD distributions. For most materials, the SGD distribution is very close to the measured data.

Quantitative Error Measure

For each material, we define the fitting error as the L 2 norm of the difference between measured data and the Cook-Torrance BRDF: To ensure a fair comparison between bright and dark materials, we normalize this error by dividing it with the maximum albedo of the BRDF, as in [START_REF] Durand | Experimental analysis of BRDF models[END_REF] (the supplemental has the un-normalized error value). Figure 11 compares the fitting errors for the Cook-Torrance BRDF using the SGD and Beckmann distributions (parameters for Beckmann from [START_REF] Durand | Experimental analysis of BRDF models[END_REF]). We sorted the materials by increasing α roughness, going from highly specular to diffuse. For all but 3 of the materials (black-fabric, yellow-matte-plastic, and white-paint), the SGD distribution provides the best approximation. For many materials, we improve the accuracy by one order of magnitude, and for some, such as hematite, by two orders of magnitude.

E = (m(i, o) -ρ(i, o)) 2 cos θ i cos θ o dω i
For the materials where we do not improve over Beckmann distribution, we think that the problem comes from the fitting algorithm rather than the SGD distribution. Man-ually setting the parameters for these materials improves the accuracy (all the parameters we use in this paper were computed in a single run of our optimization process, without any tweaking for specific materials).

To evaluate our fitting method, we used it to compute parameters for the Beckmann and TR/GGX distributions, and reported the error for each material in Figure 11. For almost all materials, the error is higher than with Beckmann distribution and parameters from [START_REF] Durand | Experimental analysis of BRDF models[END_REF]. Our fitting method works better if the shape of the distribution matches the measured data.

Figure 12 provides a pixel-by-pixel comparison for a horizontal scanline of rendered image between: measured reflectance, Cook-Torrance with Beckmann distribution and SGD distribution, with and without importance sampling. The Beckmann distribution overestimates specular lobes; SGD remains very close to the reference. The figure also validates that using GGX importance sampling for SGD distribution gives the same results, but reduces the noise.

Timings

Since our algorithm only uses two slices of the BRDF measurement for fitting the parameters, it is extremely fast: 2.5 minutes on average to fit all the parameters for a single material on a single core 2.57 GHz Intel CPU. For 65 % of the materials, the fitting process took less than 1 minute. We also measured the cost of evaluating our reflectance model inside a ray-tracer, using valgrind profiling tool. A single evaluation takes 3044 CPU cycles, compared to 1416 with Beckmann and 551 with Lafortune. Our model is more expensive because we estimate the BRDF independently for each color channel.

Limitations

For some materials in the MERL database, even with the SGD distribution, we see evidence of a multi-lobe behavior. This is quite obvious for two-layer-gold and two-layersilver (see Figure 13), and it appears (but it's less obvious) for alum-bronze. For these materials, adding a second lobe would improve the accuracy. However, the number of materials with multi-lobe behavior is 3 out of 100.

Our fitting method is based on only two slices of the material and on the assumption that the material follows the The white-paint material illustrates a failure case of our fitting algorithm (see Figure 14). The error with SGD is larger than with Beckmann. The difference is clearly visible in the rendered pictures (Figure 14(b)). A possible explanation is visible in the lobes (Figure 14(c)): the Fresnel term is almost null at normal incidence, and our fitting algorithm does not pick the right shape for the specular lobe.

Conclusion and Future work

We have presented the SGD micro-facet probability distribution function for the Cook-Torrance BRDF. This distribution provides an accurate fit for most measured materials. We have also presented a new fitting algorithm, where we fit each color channel independently (instead of precomputing the diffuse and specular colors), and we fit using only two slices of the BRDF. This fitting algorithm is very efficient when combined with the SGD distribution, taking 2.5 mn to compute the parameters for a measured distribution.

In the supplemental, we provide parameters for the SGD distribution for all materials in the MERL database, as well as GLSL code. We hope that this will help researchers and software developpers in using the SGD distribution.

In future work, we want to continue working on microfacet distributions, finding a distribution that provides the same accurate fit to measured data while being easier to compute and integrating into nicer functions. We also want to target material acquisition: we describe an acquired material accurately with only 18 coefficients. Can we use this property for faster acquisition of new materials?

Figure 2 :

 2 Figure 2: For Cook-Torrance BRDF, the material microgeometry is a random distribution of specular micro-facets. Angles are relative to the normal n of the macro-geometry.

  SGD , a=3e-4, p=0.37 (b) The SGD distribution

Figure 3 :

 3 Figure3: The micro-facet probability distribution for brass extracted from the measured data. The SGD distribution (right) fits the data accurately both at the peak and the tail, unlike existing distributions(left)

Figure 4 :

 4 Figure 4: The SGD distribution is an accurate fit for a wide range of materials.

  grazing angles, it decreases to 0 instead of increasing to 1. For some materials, we observe a linear slope, different from Schlick's approximation.

Figure 6 :

 6 Figure 6: The Fresnel term extracted from the measured data does not behave as predicted by the theory

Figure 7 :

 7 Figure 7: Uniform and importance sampling for specularviolet-phenolic with the same rendering time (6 mn). φ m = 2πu 1 m = (cos φ m sin θ m , sin φ m sin θ m , cos θ m ) o = 2 |i • m| m-i

Figure 11 :

 11 Figure 11: Normalized fitting errors (logarithmic scale) of the Cook-Torrance model with Beckmann and SGD distributions. In most cases, SGD provides a much better fit.

  Lafortune Lab error (g) Beckmann Lab error (h) TR/GGX Lab error (i) SGD Lab error (ours)

Figure 8 :Figure 9 :

 89 Figure 8: Comparison between the Cook-Torrance model with Beckmann, TR/GGX and SGD distributions, Lafortune and ground truth for aventurine from the MERL database (spelled aventurnine in [NDM05]).

  Lafortune Lab error (g) Beckmann Lab error (h) TR/GGX Lab error (i) SGD Lab error (ours)

Figure 10 :

 10 Figure 10: Comparison between the Cook-Torrance model with Beckmann, TR/GGX and SGD distributions, Lafortune and ground truth for colonial-maple-223 from the MERL database.

Figure 12 :

 12 Figure 12: Pixel by pixel comparison between the reference, Beckmann and SGD (with and without importance sampling) for aventurine from MERL database.

Figure 13 :

 13 Figure 13: An example of a two-layer material, two-layersilver, that requires two lobes for accurate fitting.

MFigure 14 :

 14 Figure 14: white-paint, a failure case for our fitting algorithm. Cook-Torrance model. It will miss behavior that are outside of the model, for example color-changing-paint.

used spherical Gaussians to approximate existing reflectance models, in- cluding Cook-Torrance and Lafortune. The convolution of two spherical Gaussians is another spherical Gaussian, so BRDF expressed this way are easier to convolve with envi- ronment maps or normal distributions in the same model. Romeiro et al. [RVZ08] and Pacanowski et al. [PSCS * 12

  et al. [WRG * 09]

	]
	project measured BRDFs on a two-dimensional space
	(θ d , θ h ). Pacanowski approximates this projection with ratio-
	nal fractions, compressing the BRDF data down to 200 KB.

c 2012 The Author(s) c 2012 The Eurographics Association and Blackwell Publishing Ltd.

† F. Durand, personal communication. c 2012 The Author(s) c 2012 The Eurographics Association and Blackwell Publishing Ltd.

We fit the probability distribution parameters (α, p) to the measured data for varying θ h , with θ d = 0.

We fit the Fresnel term parameters (F 0 , F 1 ) to the measured data for varying θ d , with θ h = 0. c 2012 The Author(s) c 2012 The Eurographics Association and Blackwell Publishing Ltd.

c 2012 The Author(s) c 2012 The Eurographics Association and Blackwell Publishing Ltd.