Dennis Diefenbach
email: dennis.diefenbach@univ-st-etienne.fr

Kuldeep Singh
email: kuldeep.singh@iais.fraunhofer.de

Andreas Both

Didier Cherix
email: didier.cherix@gmail.com

Christoph Lange

Sören Auer

The Qanary Ecosystem: getting new insights by composing Question Answering pipelines

Keywords: Semantic Web, Software Reusability, Question Answering, Service Composition, Semantic Search, Ontologies, Annotation Model II D

The field of Question Answering (QA) is very multi-disciplinary as it requires expertise from a large number of areas such as natural language processing (NLP), artificial intelligence, machine learning, information retrieval, speech recognition and semantic technologies. In the past years a large number of QA systems were proposed using approaches from different fields and focusing on particular tasks in the QA process. Unfortunately, most of these systems cannot be easily reused, extended, and results cannot be easily reproduced since the systems are mostly implemented in a monolithic fashion, lack standardized interfaces and are often not open source or available as Web services. To address these issues we developed the knowledge-based Qanary methodology for choreographing QA pipelines distributed over the Web. Qanary employs the qa vocabulary as an exchange format for typical QA components. As a result, QA systems can be built using the Qanary methodology in a simpler, more flexible and standardized way while becoming knowledgedriven instead of being process-oriented. This paper presents the components and services that are integrated using the qa vocabulary and the Qanary methodology within the Qanary ecosystem. Moreover, we show how the Qanary ecosystem can be used to analyse QA processes to detect weaknesses and research gaps. We illustrate this by focusing on the Entity Linking (EL) task w.r.t. textual natural language input, which is a fundamental step in most QA processes. Additionally, we contribute the first EL benchmark for QA, as open source. Our main goal is to show how the research community can use Qanary to gain new insights into QA processes.

Introduction

The amount of data, information, and knowledge available on the Web and within enterprise environments is increasing constantly. Especially in enterprise environments a strong trend to better connected data can be observed, leading to interlinked and accessible data unlocking the company's information for intense data analytics and information retrieval. Novel interfaces are required for enabling users to retrieve information in such scenarios and interact with it. Natural language interfaces are being considered to bridge the gap between large amounts of (semi-structured) data and users' needs. Recent industrial applications show the capabilities and advantages of natural language interfaces in the field of Question Answering (QA). These include Apple Siri 6 , Microsoft Cortana 7 , and "Ok Google" 8 . However, these proprietary platforms do not facilitate experimentation with cutting-edge research approaches, they offer only limited interfaces for integrating third-party components and they are generally not open, reusable and extensible by developers and the research community.

Several QA systems have been developed recently in the research community, for example, [START_REF] Shekarpour | SINA: Semantic interpretation of user queries for question answering on interlinked data[END_REF][START_REF] Freitas | Treo: combining entity-search, spreading activation and semantic relatedness for querying linked data[END_REF][START_REF] Cabrio | QAKiS: an open domain QA system based on relational patterns[END_REF][START_REF] Dima | Answering natural language questions with intui3[END_REF]. These systems perform well in specific domains, but their reusability for further research is limited because of their focus on specific technologies, applications or datasets. As a result, creating new QA systems is currently still cumbersome and inefficient. Particularly, the research community is not empowered to focus on improving particular components of the QA process, as developing a new QA system and integrating a component is extremely resource-consuming. Some first steps for developing flexible, modular QA systems have started to address this challenge, e.g., [START_REF] Marx | Towards an open question answering architecture[END_REF][START_REF] Ferrández | The QALL-ME framework: A specifiable-domain multilingual Question Answering architecture[END_REF]. However, these approaches lack several key properties required for constructing QA systems in a community effort as they are, for example, bound to a particular technology environment and have rather static interfaces, which do not support the evolution of the inter-component data exchange models. For this reason we presented the qa vocabulary [START_REF] Singh | Towards a message-driven vocabulary for promoting the interoperability of question answering systems[END_REF] as a flexible and extensible data model for QA systems. Based on the vocabulary, we developed the Qanary [START_REF] Both | Qanary -a methodology for vocabulary-driven open question answering systems[END_REF] methodology for integrating components into QA systems; it is independent from programming languages, agnostic to domains and datasets, as well as enabled for components on any granularity level within the QA process.

This work presents the Qanary ecosystem: the components and services currently implemented around the qa vocabulary by using the Qanary methodology. We present a general workflow that can be used to construct and particularly analyze as well as optimize future QA systems in a community effort using the Qanary ecosystem. It can be broken down into two phases: (1.) the identification and integration of existing state-of-the-art approaches to solve a particular task in the QA pipeline, and (2.) the derivation of benchmarks for sub-tasks of a QA process from well-known QA benchmarks such as the Question Answering over Linked Data (QALD) challenge 9 . Hence, the described approach is dedicated to support the engineering process to build components for a QA system and the system by itself, by using the knowledge-driven approach for flexible component integration and quality evaluations. In this paper, we show this workflow applied to the task of EL, which is key in the QA process. Therefore, we consider components dedicated to the tasks of named entity identification/recognition (NER) and named entity disambiguation (NED), which are integrated into the Qanary ecosystem. The included components are the NER tool of DBpedia Spotlight [START_REF] Mendes | DBpedia spotlight: Shedding light on the web of documents[END_REF], the Stanford NER tool [START_REF] Finkel | Incorporating non-local information into information extraction systems by Gibbs sampling[END_REF] and the Federated knOwledge eXtraction Framework (FOX) [START_REF] Speck | Ensemble learning for named entity recognition[END_REF] as well as the NED components Agnostic Disambiguation of Named Entities Using Linked Open Data (AGDISTIS) [START_REF] Usbeck | AGDISTIS -graph-based disambiguation of named entities using linked data[END_REF] and the named entity disambiguator of DBpedia Spotlight. In addition two combined approaches for NER and NED are also provided as components: IBM Alchemy10 and Lucene Linker -a component that we implemented following the idea of the QA system SINA [START_REF] Shekarpour | SINA: Semantic interpretation of user queries for question answering on interlinked data[END_REF]. Moreover, we devised a benchmark for entity linking (EL) based on the well-known Question Answering over Linked Data (QALD) challenge. Our contribution here has three aspects. First, we provide researchers with a tool for comparing NED and NER w.r.t. QA, thus enabling them to compare their components with the state-of-the-art just by implementing a Qanary wrapper around their novel functionality. Second, we provide the results of comparing existing tools, i.e., an expressive benchmark for the quality of entity linking components w.r.t. natural language questions, thus enabling the QA community to gain new insights into QA processes. Third, we compute a list of questions that are completely annotated w.r.t. the entity linking process. Hence, researchers investigating a processing step of a QA system that comes after entity linking can reuse these annotations to create an environment for conveniently testing and continuously improving their components.

As a result, the QA community is empowered to easily reuse entity linking functionality for QA systems (or for the development of other tools depending on named entities) and reuse a profound benchmark for QA systems both for the evaluation of new entity linking components and as input for components active in the subsequent processing steps of a QA system (e.g., relation detection or query computation). However, the entity linking functionality and experiments presented in this paper are just a proof that Qanary's knowledge-driven and component-driven approach as well as the previously described general workflow provides key advantages particularly in contrast to existing systems and other benchmarks.

The next section describes related work. Sec. 3 gives an overview of our recent work which laid the groundwork for the Qanary ecosystem. Sec. 4 gives an overview of the components and services that are available in the Qanary ecosystem. Sec. 5 describes how the Qanary ecosystem can be used to gain new insights into QA processes w.r.t. the EL task. Sec. 6 concludes and points to future research areas.

Related Work

In the context of QA, a large number of systems and frameworks have been developed in the last years. This can be observed for example from the number of QA systems (> 20 in the last 5 years) that were evaluated against the QALD benchmark. Many QA systems use similar techniques. For example, there are services for named entity identification (NER) and disambiguation (NED) such as DBpedia Spotlight [START_REF] Mendes | DBpedia spotlight: Shedding light on the web of documents[END_REF] and Stanford NER [START_REF] Finkel | Incorporating non-local information into information extraction systems by Gibbs sampling[END_REF], which are reused across several QA systems. These reasons led to the idea of developing component-based frameworks that make parts of QA systems reusable. We are aware of three frameworks that attempt to provide a reusable architecture for QA systems. The first is QALL-ME [START_REF] Ferrández | The QALL-ME framework: A specifiable-domain multilingual Question Answering architecture[END_REF] which provides a reusable architecture skeleton for building multilingual QA systems. The second is openQA [START_REF] Marx | Towards an open question answering architecture[END_REF], which provides a mechanism to combine different QA systems and evaluate their performance using the QALD-3 benchmark. The third is the Open KnowledgeBase and Question-Answering (OKBQA) challenge 11 . It is a community effort to develop a QA system that defines rigid JSON interfaces between the components. Differently from these works we do not propose a rigid skeleton for the QA pipeline, instead we allow multiple levels of granularity and enable the community to develop new types of pipelines.

Recognizing named entities in a text and linking them to a knowledge base is an essential task in QA. DBpedia Spotlight [START_REF] Mendes | DBpedia spotlight: Shedding light on the web of documents[END_REF], Stanford NER [START_REF] Finkel | Incorporating non-local information into information extraction systems by Gibbs sampling[END_REF], FOX [START_REF] Speck | Ensemble learning for named entity recognition[END_REF], and Alchemy API are a few of the tools dedicated to such tasks. Furthermore, tools such as DBpedia Spotlight, AGDISTIS [START_REF] Usbeck | AGDISTIS -graph-based disambiguation of named entities using linked data[END_REF], Alchemy API etc. not only identify information units in text queries but also point every named entity to a knowledge resource for disambiguation.

We are not aware of any work that has tried to compare in a systematic way existing approaches that tackle sub-processes of QA pipelines, for example EL. Atdag and Labatut [START_REF] Atdag | A comparison of named entity recognition tools applied to biographical texts[END_REF] compare a few NER tools applied to bibliographic text, whereas researchers in [START_REF] Rizzo | NERD: A framework for unifying named entity recognition and disambiguation extraction tools[END_REF] present NERD, a framework for evaluating NER tools in the context of Web data where a wrapper of NER/NED services was implemented but the independent registration of new services is not possible. Platforms such as GERBIL [START_REF] Usbeck | GERBIL: General entity annotator benchmarking framework[END_REF] and GERBIL for QA 12 offer benchmarks for EL tools and full QA systems and they generate persistent URIs for experiment results. This enables third-party evaluations and citable URIs. Their main goal is not to gain new insights into the underlying processes but only to generate one final metric that is publishable. For example, they do not generate a summary indicating in which cases the corresponding tool succeeded or failed. In contrast, the Qanary reference implementation is a full-featured framework for component-oriented QA process creation, which is additionally enabled to support benchmarking of the included distributed components. We give a comparison of the described tools in Table 1

The qa Vocabulary and the Qanary Methodology

To advance the QA process, researchers are combining different technologies to optimize their approaches. However, reusability and extensibility of QA components and systems remains a major hurdle. There are many components and services, which are provided as standalone implementations but can be useful in QA processes (e.g., the previously mentioned DBpedia Spotlight, AGDISTIS etc.), but there has so far not been a methodology to integrate them within QA pipelines. Instead substantial programming efforts had to be invested as each component provides its own API or integration method.

To address this challenge, and to promote reusability and extensibility of QA components, we introduced the qa vocabulary [START_REF] Singh | Towards a message-driven vocabulary for promoting the interoperability of question answering systems[END_REF]. This vocabulary can represent information that is generated during the execution of a QA pipeline when processing a question given as speech or text input. Consider, for example, the question "When was Barack Obama born?". Typical information generated by components of a QA pipeline are the positions of named entities (NE) (such as "Barack Obama"), the ontological relations used to express the relational phrase in the question (that "born" refers to dbo:birthPlace 13 ), the expected answer type (here: a date), the generated SPARQL query, the language of the question and possible ontologies that can be used to answer it.

The rationale of qa is that all these pieces of information can be expressed as annotations to the question. Hence, these exposed pieces of information can be provided as an (RDF) knowledge base containing the full descriptive knowledge about the currently given question.

qa is built on top of the Web Annotation Data Model (WADM) 14 , a vocabulary to express annotations. The basic constructs of the WADM are annotations with at least a target indicating what is described and a body indicating the description.

PREFIX oa : < http :// www . w3 . org / ns / oa #> <anno > a oa : Annotation ; In qa, a question is assumed to be exposed at some URI (e.g. URIQuestion that can be internal and does not need to be public) and is of type qa:Question. Similarly other QA concepts (qa:Answer, qa:Dataset, etc.) are defined in the vocabulary; please see [START_REF] Singh | Towards a message-driven vocabulary for promoting the interoperability of question answering systems[END_REF] for further details. As a result, when using qa, the knowledge of the QA system is now representable independently from a particular programming language or implementation paradigm because everything is represented as direct or indirect annotations of a resource of type qa:Question. The qa vocabulary is published at the persistent URI https://w3id.org/wdaqua/qanary# under the CC0 1.0 license 15 .

The qa vocabulary led to the Qanary methodology [START_REF] Both | Qanary -a methodology for vocabulary-driven open question answering systems[END_REF] for implementing processes operating on top of the knowledge about the question currently processed within a QA system, leading to the possibility of easy-to-reuse QA components. All the knowledge related to questions, answers and intermediate results is stored in a central Knowledge Base (KB). The knowledge is represented in terms of the qa vocabulary in the form of annotations of the relevant parts of the question.

Within Qanary the components all implement the same service interface. Therefore, all components can be integrated into a QA system without manual engineering effort. Via it's service interface a component receives information about the KB (i.e., the endpoint) storing the knowledge about the currently processed question of the user. Hence, the common process within all components is organized as follows:

1. A component fetches the required knowledge via (SPARQL) queries from the KB. In this way, it gains access to all the data required for its particular process. 2. The custom component process is started, computing new insights of the user's question. 3. Finally, the component pushes the results back to the KB (using SPARQL). Therefore, after each process step (i.e., component interaction), the KB should be enriched with new knowledge (i.e., new annotations of the currently processed user's question). This way the KB keeps track of all the information generated in the QA process even if the QA process is not predefined or not even known. A typical QA pipeline consists of several steps such as NER, NED, relation identification, semantic analysis, query computation and result ranking. Most recently we provided a reference implementation of Qanary [START_REF] Singh | Qanary-the fast track to create a question answering system with linked data technology[END_REF]. We call this implementation message-driven; it follows the architectural pattern that we have previously described for search engines in [START_REF] Both | A service-oriented search framework for full text, geospatial and semantic search[END_REF]. The processing steps might be implemented in different components with dedicated technology provided by distinguished research groups. The message-driven implementation of Qanary [START_REF] Both | A service-oriented search framework for full text, geospatial and semantic search[END_REF] laid foundations for the QA ecosystem. The advantage of such an ecosystem is that it combines different approaches, functionality, and advances in the QA community under a single umbrella.

The Qanary Ecosystem

The Qanary ecosystem consists of a variety of components and services that can be used during a QA process. We describe in the following what components and services are available. The Qanary ecosystem includes various components covering a broad field tasks within QA systems. This includes different components performing NER like FOX [START_REF] Speck | Ensemble learning for named entity recognition[END_REF] and Stanford NER [START_REF] Finkel | Incorporating non-local information into information extraction systems by Gibbs sampling[END_REF] and components computing NED such as DBpedia Spotlight and AGDISTIS [START_REF] Usbeck | AGDISTIS -graph-based disambiguation of named entities using linked data[END_REF]. Also industrial services such as the Alchemy API are part of the ecosystem. Furthermore, Qanary includes a language detection module [START_REF] Nakatani | Language detection library for java[END_REF] to identify the language of a textual question. A baseline automatic speech recognition component is also included in the reference implementation. It translates audio input into natural language texts and is based on Kaldi 16 . Additionally it should be noted that a monolithic QA system component was developed in the course of the WDAqua project 17 and is integrated in Qanary. Additional external QA components are included in the ecosystem. In particular, Qanary includes two components from the OKBQA challenge 18 namely the template generation and disambiguation component. All components are implemented following the REST principles. Hence, these tools/approaches become easy to reuse and can now be invoked via transparent interfaces. To make it easy to integrate a new component we have created a Maven archetype that generates a template for a new Qanary component 19 . The main services are encapsulated in the Qanary Pipeline. It provides, for example, a service registry. After being started, each component registers itself to the Qanary Pipeline central component following the local configuration 20 of the component. Moreover, the Qanary Pipeline provides several web interfaces for machine and also human interaction (e.g., for assigning a URI to a textual question, retrieving information about a previous QA process, etc.). Particularly, as each component automatically registers itself to the Qanary Pipeline, a new QA system can be created and executed just by on-demand configuration (a concrete one is shown in Fig. 1). Hence, the reference implementation already provides the features required for QA systems using components distributed over the Web.

An additional interface allows for benchmarking a QA system created on demand using Gerbil for QA 21 , thus allowing third-party evaluation and citeable URIs. Fig. 2 illustrates the complete reference architecture of Qanary and a few of its components. Additional services include a user interface for a fully working QA system. A running demo can be found at http://www.wdaqua.eu/qa. 16 http://kaldi-asr.org 17 http://www.wdaqua.eu 18 http://www.okbqa.org/ 19 https://github.com/WDAqua/Qanary/wiki/How-do-I-integrate-a-new-component-in-Qanary% 3F 20 The configuration property spring.boot.admin.url defines the endpoint of the central component (and can be injected dynamically). The code is maintained in the repository at https://github.com/WDAqua/Qanary under the MIT License 22 .

5 Gaining new insights into the QA process: The EL task

To show how Qanary can be used to gain new insights into QA processes we focus here on the EL task. We present the qa vocabulary used to represent the information produced by NER and NED tools. Moreover we describe the components of the Qanary ecosystem that are integrated using the Qanary methodology and that can be used for the EL task. We describe how we constructed a benchmark for EL out of QALD. The analysis of the benchmark will show: what are the best tools to tackle QALD, where are current research gaps, and for which questions do single tools fail and why.

Finally, we present a new dataset that can be used as a gold standard for a sub-task of the QA process.

The following workflow is not restricted to the EL task but can be applied to any other sub-task of the QA process to gain new insights into QA processes.

The Qanary vocabulary for the EL task

The qa vocabulary is designed to be extensible so as not to constrain the creativity of the QA community developers. All information that can possibly be generated and that might need to be shared across QA components can be expressed using new annotations. This principle follows the understanding that standards that allow communication between QA components must be defined by the community. Taking into consideration the state-of-the-art (e.g., [START_REF] Auer | DBpedia: A nucleus for a web of open data[END_REF][START_REF] Usbeck | AGDISTIS -graph-based disambiguation of named entities using linked data[END_REF][START_REF] Finkel | Incorporating non-local information into information extraction systems by Gibbs sampling[END_REF]), the qa vocabulary was extended with standard concepts for NER and NED representations. This in particular uniforms the representation of the input and output of every integrated component, making it easy to compare and analyze the integrated tools. Note that this does not only hold for tools that can be used for EL but for every tool integrated into the Qanary ecosystem.

To describe an entity spotted within a question we introduced a dedicated annotation: qa : AnnotationOfSpotInstance a owl : Class ; rdfs : subClassOf qa : AnnotationOfQuestion .

If in the question "When was Barack Obama born?" a spotter detects "Barack Obama" as an NE, this fact can be expressed by the following annotation, where oa:SpecificResource and oa:hasSelector are concepts of the WADM to select a part of a text. For named entities, we define the new concept qa:Named Entity and a corresponding annotation subclass (i.e., annotations of questions whose body is an instance of qa:NamedEntity): qa : NamedEntity a owl : Class ; qa : AnnotationOfInstance a owl : Class ; owl : equivalentClass [ a owl : Restriction ; owl : onProperty oa : hasBody ; owl : someValuesFrom qa : NamedEntity ] ; rdfs : subClassOf qa : AnnotationOfQuestion .

If an NED tool detects in the question "When was Barack Obama born?" that the text "Barack Obama" refers to dbr:Barack_Obama 23 , then this can be expressed (using oa:hasBody) as: Note that using annotations provides many benefits thanks to the inclusion of additional metadata such as the creator of the information, the time and a trust score. However, this information is omitted here for readability.

Reusable NER and NED components

The following components integrated into the Qanary ecosystem solve the task of NER, NED or the combined task of EL.

-Stanford NER (NER) is a standard NLP tool that can be used to spot entities for any ontology, but only for languages where a model is available (currently English, German, Spanish and Chinese) [START_REF] Finkel | Incorporating non-local information into information extraction systems by Gibbs sampling[END_REF]. -FOX (NER) integrates four different NER tools (including the Stanford NER tool) using ensemble learning [START_REF] Speck | Ensemble learning for named entity recognition[END_REF]. -DBpedia Spotlight spotter (NER) uses lexicalizations, i.e., ways to express named entities, that are available directly in DBpedia [START_REF] Mendes | DBpedia spotlight: Shedding light on the web of documents[END_REF]. -DBpedia Spotlight disambiguator (NED), the NED part of DBpedia Spotlight, disambiguates entities by using statistics extracted from Wikipedia texts [START_REF] Mendes | DBpedia spotlight: Shedding light on the web of documents[END_REF].

-AGDISTIS (NED) is a NED tool that uses the graph structure of an ontology to disambiguate entities [START_REF] Usbeck | AGDISTIS -graph-based disambiguation of named entities using linked data[END_REF]. -ALCHEMY (NER + NED): Alchemy API 24 is a commercial service (owned by IBM) exposing several text analysis tools as web services. -Lucene Linker (NER + NED) is a component that we implemented following the idea of the SINA QA system [START_REF] Shekarpour | SINA: Semantic interpretation of user queries for question answering on interlinked data[END_REF], which employs information retrieval methods.

Note that thanks to the integration as Qanary components all these tools can be interwoven, i.e., each NER tool can be combined with each NED tool just by configuration.

A QALD-based benchmark for EL in QA

To compare the different entity linking approaches, we created a benchmark based on the QALD (Question Answering over Linked Data) benchmark used for evaluating complete QA systems. The QALD-6 training set 25 , which is the recent successor of QALD-5 [START_REF] Unger | Question answering over linked data (QALD-5)[END_REF], contains 350 questions, including the questions from previous QALD challenges. For each question, it contains a SPARQL query that retrieves the corresponding answers. For example, the following SPARQL query corresponds to the question "Which soccer players were born on Malta?".

PREFIX dbr : < http :// dbpedia . org / resource /> PREFIX dbo : < http :// dbpedia . org / ontology /> SELECT DISTINCT ? uri WHERE { ? uri a dbo : SoccerPlayer . ? uri dbo : birthPlace dbr : Malta . } EL tools should provide functionality to interlink the named entities present in the question with DBpedia (or other data), i.e., they should be able to identify "Malta" and link to it the resource http://dbpedia.org/resource/Malta. Our benchmark compares the URIs generated by an EL tool with the resource URIs in the SPARQL query (i.e., those in the http://dbpedia.org/resource/ namespace) 26 , which are obviously required for answering the question. Hence the gold standard for each question is given by all resource URIs in the SPARQL query. 27 24 http://alchemyapi.com 25 Training Questions of Task 1: http://qald.sebastianwalter.org/index.php?x= challenge&q=6 26 Note that resources of the type http://dbpedia.org/ontology/* would match a DBpedia property or class and therefore are not considered here. 27 This definition of the gold standard ignores the order of the URIs. In practice this definition rarely causes problems, but in theory one could construct counter-examples that pinpoint the limitations. Imagine the question "What German actors were not born in Germany?", and imagine that the word "German" got linked to the entity dbr:Germany and "Germany" to dbr:Germans -clearly a wrong linking, but "correct" w.r.t. our gold standard definitions. However, in QALD there are no questions in which such a mix-up is likely to happen.

Precision(q) =

# correct URIs retrieved by the EL configuration for q # URIs retrieved by the EL configuration identifying NE in q Recall(q) = # correct URIs retrieved by the EL configuration for q # gold standard answers for q F1-measure(q) =2 × Precision(q) × Recall(q) Precision(q) + Recall(q) Fig. 3. Metrics used in the EL benchmark

The metrics for a question q are calculated as defined in the QALD benchmark and are reported in Fig. 3 28 . The metrics over all questions are defined as the average of the metrics over the single questions. The corresponding benchmark component is available at https://github.com/WDAqua/Qanary.

Note that this procedure can be generalized and applied to many sub-processes of a QA pipeline. For example, one might establish a benchmark to recognize relations or classes, a benchmark to identify the type of the SPARQL query required to implement a question (i.e., a SELECT or an ASK query), a benchmark for identifying the answer type (i.e., list, single resource, . . . ) and so on.

We used our benchmarking resource described above to evaluate EL tools. We have identified different strategies to annotate entities in questions. These include using the spotters Stanford NER, FOX, DBpedia Spotlight Spotter, the NED tools AGDISTIS, and the DBpedia Spotlight disambiguator, as well as the (monolithic w.r.t. NER and NED) EL tools Alchemy and Lucene Linker. Each of them is implemented as an independent Qanary component, as presented in Sec. 5.2. According to the Qanary methodology the computed knowledge about a given question is represented in terms of the qa vocabulary and can be interpreted by the benchmark component.

For the benchmark all three NER components are combined with each of the two NED components. All questions of QALD-6 are processed by each of the six resulting configurations, and by the two monolithic tools. The benchmark was executed exclusively using the service interface of the Qanary Pipeline.

Table 2 shows the benchmark results. The "Fully detected" column indicates the number of questions q where some resources were expected and the EL configuration achieved Recall(q)=1. The column "Correctly Annotated" indicates for how many questions we obtained Precision(q)=Recall(q)=1. Finally, the table shows for each configuration the precision and recall metrics over all questions. 28 In the corner cases where the number of system answers or the number of gold standard answers is zero we follow the same rules that are used in the QALD evaluation; see https://github.com/ag-sc/QALD/blob/master/6/scripts/evaluation.rb. 2. Benchmark of the QALD-6 data using the Qanary reference implementation.

Discussion

We presented the Qanary methodology, which allows to interweave the analysed tools. Thanks to the qa vocabulary we can collect (from the SPARQL endpoint) the results produced by every configuration. A detailed overview showing for each question if the pipeline configurations lead to a recall resp. F-measure of 1 can be found at:

https://raw.githubusercontent.com/WDAqua/Qanary/master/ICWE-results/

• Recall_1.csv and • F-measure_1.csv.

We analysed both this data and the results presented in Table 2 to draw some conclusions on the performance of the used tools with respect to QALD. For some QALD-6 questions none of the pipeline configurations is able to find the required resources, for example:

-Q1: "Give me all cosmonauts." with the following resources requested in the SPARQL query: dbr:Russia, dbr:Soviet_Union. For this question one should be able to understand that cosmonauts are astronauts born either in Russia or in the Soviet Union. Detecting such resources would require a deep understanding of the question. Q201 is similar: "Give me all taikonauts.". -Q13: "Are tree frogs a type of amphibian?"; requested resources: dbr:Hylidae, dbr:Amphibian.

The problem here is that the scientific name of "tree frogs" is Hylidae and there is no such information in the ontology except in the free text of the Wikipedia abstract.

-Q311: "Who killed John Lennon?"; requested resource: dbr:Death_of_John_ Lennon.

The problem is that one would probably assume that the information is encoded in the ontology as a triple like "John Lennon", "killed by", "Mark David Chapman" but this is not the case. Even if in the question the actual NE is "John Lennon", DBpedia happens to encode the requested information in the resource "Death of John Lennon". A similar case is Q316 ("Which types of grapes grow in Oregon?"), where the resource dbr:Oregon_wine is searched.

Spotter comparison An unexpected result is that FOX as a spotter has a lower recall than the Stanford NER tool, even though FOX also includes the results of Stanford NER. This can be seen from comparing the recall of the configurations that combine these tools with AGDISTIS or the DBpedia Spotlight disambiguator. The reason is that, for example, in Q101 ("Which German cities have more than 250,000 inhabitants?") the word "German" is tagged by the Stanford NER tool as "MISC" (miscellaneous). However, FOX only supports the tags "PERS" (person), "ORG" (organisation), and "LOC" (location). This explains why FOX has a lower recall but a higher precision than Stanford NER.

The spotters based on NLP (e.g., Stanford NER and FOX) perform worse than the DBpedia Spotlight Spotter, which is mainly based on vocabulary matching. Syntactic features do not suffice to identify "Prodigy" in Q114 ("Give me all members of Prodigy.") or "proinsulin" in Q12 ("Is proinsulin a protein?"). Moreover, there are cases like Q109 ("Give me a list of all bandleaders that play trumpet."), where bandleaders is not an NE in the NLP sense but is modeled as a resource in the DBpedia ontology. Similarly, in Q133 ("Give me all Australian nonprofit organizations."), the resource dbr:Australia is expected for the adjective "Australian".

NED comparison

The results show that the DBpedia Spotlight disambiguator performs better than AGDISTIS w.r.t. QA. AGDISTIS works on co-occurrences of NE. These occur often in longer texts but are rare in questions. If only one NE is spotted, AGDISTIS can only decide based on the popularity of the resources but not on the context as DBpedia Spotlight does.

EL comparison

The best spotter, the DBpedia Spotlight spotter, and the best NED, the DBpedia Spotlight disambiguator, also perform best in the EL task. Only the Lucene Linker has a higher recall but must be followed by a disambiguation tool in the next step to increase precision. The Alchemy API shows the lowest recall.

Our evaluation does not permit the conclusion that the combination of DBpedia Spotlight spotter and disambiguator should be recommended in general. The best choice may depend on the questions and on the particular form of dataset. The DBpedia Spotlight disambiguator, for example, is tightly connected to Wikipedia; even its algorithm cannot be ported to other ontologies. Alchemy, despite showing a very low F 1 -score and recall, could be a useful resource for QA over other datasets, such as Freebase or Yago. This is one of the many reasons that makes Qanary in general a valuable resource. For a new QA scenario, Qanary empowers developers to quickly combine existing tools and more easily determine the best configuration. Moreover, a detailed analysis of the configurations can help to detect the main problems of the different strategies to further improve the complete QA process or just individual components. Hence, using Qanary provides insights on the quality of each component w.r.t. the current use case, leading to an optimization of the system based on the given data.

A combination of tools solving the same task in an ensemble learning approach is now possible and is recommended as the benchmark results already indicate. Note that such an analysis is not possible using existing benchmarking tools such as Gerbil or Gerbil for QA since they only provide a final overall score. On the other hand such an analysis is needed to detect existing research gaps and push the advancement of QA further. Hence, following the Qanary methodology the research community is enabled to develop new QA processes and components in a joint engineering effort and to validate the given quality metrics within the specific QA scenario. This again proves the potential impact of Qanary within the engineering process of QA systems.

Dataset of Annotated Questions for Processing in QA systems

We provide a new dataset with questions of the QALD-6 benchmark, which are completely annotated with disambiguated named entities (DBpedia resource URIs) computed by applying our benchmarking to the EL configurations described in Sec. 5.3. This dataset contains 267 questions (out of 350 questions in the QALD-6 training set) because the components could not annotate the rest. A Turtle file, representing the results in terms of the qa vocabulary, is published at https://github.com/WDAqua/Qanary under the CC0 license. A typical fragment of the provided data is provided in Fig. 4.

We imagine the following usage scenarios for this dataset. It can be used as input for steps in a QA process following the EL task that require annotated named entities, such as relation detection or query computation. Consequently, QA components that depend on the output of the EL task can now be evaluated without depending on concrete EL components (and without the results being influenced by possible flaws). Hence, in conjunction with the SPARQL queries already defined in QALD-6, we established a new gold standard for evaluating parts of a QA process. We also provide the component for computing this dataset (cf., Sec. 5.3); it can be extended if improved EL configurations are available or when a new version of the QALD benchmark is released.

Conclusion and Future Work

We have presented the status of the Qanary ecosystem, which includes a variety of components and services that can be used by the research community. These include typical components for sub-tasks of a QA pipeline as well as a number of related services.

Since all messages exchanged between components are expressed using the qa vocabulary, all information generated during a QA process can be easily kept. Thanks to this uniform message format it is now possible to easily compare existing tools and integrate new ones. Moreover, the Qanary methodology allows to integrate independent, distributed components, implemented in different programming languages in a loosely-coupled fashion. This allows the creation of comprehensive QA systems in a community effort.

Driven by the demand for better QA technology, we propose a general workflow to develop future QA systems. It mainly breaks down into two parts: (1.) the identification and integration of existing state-of-the-art approaches to solve a particular sub-task in the QA pipeline, and (2.) the derivation of a benchmark from benchmarks for QA such as QALD. Additionally a new gold standard for the sub-task can be provided. In contrast to other approaches the qa vocabulary allows to analyse a QA process. Hence, full traceability of the information used in the QA process is ensured, enabling, for example, the optimization of the assigned components. Additionally, the Qanary methodology allows to create such processes in a flexible way. This allows researchers to focus on particular tasks taking advantage of the results of the research community and contributing to it directly in a reusable way.

We have demonstrated this workflow in the case of EL. This way we realized a set of reusable components as well as the first benchmark for EL in the context of QA. All together we have shown how Qanary can be used to gain deep insights in QA processes. While having such insights the engineering process can be steered efficiently towards the improvement of the QA components. Hence, the presented engineering approach is particularly well suited for experimental and innovation-driven approaches (e.g., used by research communities).

The Qanary ecosystem is maintained and used within the WDAqua ITN project 29 (2015-2018 [10]), where Qanary is the reference architecture for new components. All artifacts are published under permissive open licenses: MIT for the software, CC0 for the datasets and the vocabulary.

One of our future task is to populate the Qanary ecosystem with any component significant to the QA community. According to the literature, the tasks of relation and answer type detection are of particular relevance, but not yet sufficiently covered by existing components. Additionally, as Qanary provides easy access to different implementations having the same purpose, ensemble learning components for all steps within a QA process are becoming possible and will increase the flexibility as well as boost overall QA quality. Hence, our overall goal is to provide a fully-featured ecosystem for creating QA components and concurrently supporting the measuring and improvement of particular QA systems w.r.t. the considered use cases. This aim provides several research challenges, e.g., the (semi-)automatic creation of self-optimizing QA systems.

  21 http://gerbil-qa.aksw.org

Fig. 1 .

 1 Fig. 1. Snapshot of the Web interface for defining a textual question and a sequence of components to process it (here only NED/NER components where registered).

Fig. 2 .

 2 Fig. 2. The Qanary reference architecture implementation highlighting the NER/NED components.

Fig. 4 .

 4 Fig. 4. Example data of Q178: "Was Margaret Thatcher a chemist?"

Table 1 .

 1 . Overview of tools related to benchmarks in the field of question answering in comparison to the benchmark functionality of Qanary.

	Property vs. Tool	NERD Gerbil Gerbil-qa Qanary
	support for analyzing NER/NED task
	support for analyzing QA process quality
	third party evaluations
	fine-grained information
	traceability of intermediate results
	computation of citable URIs

http://greententacle.techfak.uni-bielefeld.de/cunger/qald

http://www.alchemyapi.com/

http://www.okbqa.org/

Acknowledgments Parts of this work received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 642795, project: Answering Questions using Web Data (WDAqua). We would like to thank Elena Demidova for proof-reading.


Andreas Both

Kuldeep Singh

Dennis Diefenbach

Ioanna Lytra

Rapid Engineering of QA systems using the light-weight Qanary Architecture

Keywords: Software Reusability, Question Answering, Light-weight Web Architectures, Service Composition, Semantic Search, Ontologies, Annotation Model

Establishing a Question Answering (QA) system is time consuming. One main reason is the involved fields, as solving a Question Answering task, i.e., answering a user's question with the correct fact(s), might require functionalities from different fields like information retrieval, natural language processing, and linked data. The architecture used for Qanary supports the derived need for easy collaboration on the level of QA processes. The focus of the design of Qanary was to enable rapid engineering of QA systems as same as a high flexibility of the component functionality. In this paper, we will present the engineering approach leading to re-usable components, high flexibility, and easy-tocompose QA systems.

Introduction

The Web of Data is growing permanently as well as the industrial data sets. Induced by this movement the challenge for retrieving knowledge from such data sets has gained much importance in research and industry. Question Answering (QA) is tackling this challenge by providing an easy-to-use natural language interface for retrieving knowledge from large data sets. However, as QA is a challenge requiring to solve research questions from many different fields, a QA system is mostly consisting of many different components (from different research fields). Hence, enabling easy collaboration between researchers is an important engineering path while aiming at supporting the research community. Additionally, a reasonable engineering approach is required to enable a loose cooperation of different researchers.

Earlier, we established a component-oriented approach named Qanary [1] on top of a RDF vocabulary qa [START_REF] Singh | Towards a Message-Driven Vocabulary for Promoting the Interoperability of Question Answering Systems[END_REF]. This approach provides a methodology for creating QA processes using a central knowledge base (KB) to store all available QA process data. Here, we will focus on the component model and service composition following the Qanary methodology. In the demonstration, we will use the Qanary reference implementation to show the achievement w.r.t. to the rapid engineering process that was established. We will show the engineering process for creating a Qanary Web service as well as a complete Qanary-based QA system.

Related Work

In the context of QA, a large number of systems and frameworks have been developed in the last years. For example, more than 20 QA systems (in the last 5 years) were evaluated against the QALD benchmark (cf., http://qald.sebastianwalter. org). These reasons led to the idea of developing component-based frameworks that make parts of QA systems reusable. We are aware of three frameworks that attempt to provide a reusable architecture for QA systems. QALL-ME [START_REF] Ferrández | The QALL-ME framework: A specifiable-domain multilingual Question Answering architecture[END_REF] provides a reusable architecture skeleton for building multilingual QA systems. openQA [START_REF] Marx | Towards an Open Question Answering Architecture[END_REF] provides a mechanism to combine different QA systems and evaluate their performance using the QALD-3 benchmark. The Open Knowledge Base and Question Answering (OKBQA) challenge (cf., http://www.okbqa.org/) is a community effort to develop a QA system that defines rigid JSON interfaces between the components. In contrast, Qanary [START_REF] Both | Qanary -a methodology for vocabulary-driven open question answering systems[END_REF] does not propose a rigid skeleton for QA pipelines, instead we allow multiple levels of granularity, enable the community to develop new types of QA systems (not only pipelines), and focus on the research tasks.

The Qanary Component Engineering Process

Requirements The core requirements of the Qanary architecture are: ⇤ ⇥ R1 programming language independent approach, ⇤ ⇥ R2 combining of components to different QA processes as easy as possible (no predefinition of specific pattern, e.g., QA pipeline), and ⇤ ⇥ R3 enabling the researches from different communities to follow their own research tasks with as few as possible restrictions.

The Qanary Component Model Each Qanary component is an independent Web service implementing the tiny RESTful interface: process(M). Via the synchronous interface the component is triggered to process the current user question. The question (and any process data) is not contained in the message M, instead it was stored in an RDF KB. Consequently, M = (T, G i , G o ) contains the endpoint URI of the KB T and the graph G i in T containing the inbound information as well as the graph G o in T that should be used to store the computed information (i.e., outbound data flow) for further use in the QA process (by other components). Finally, the component is returning the focus to the QA process where other QA components might be called which can use the generated data. Hence, after being notified by the QA process a component will fetch the information required for its task from G i (in T) and perform its task using this information, cf., Fig. 1. To enable an easy data exchange on common ground, the RDF vocabulary qa [START_REF] Singh | Towards a Message-Driven Vocabulary for Promoting the Interoperability of Question Answering Systems[END_REF] was established (built on top of the W3C WADM, cf., w3.org/TR/annotation-model) holding the computed information as annotations of the question. Therefore, within the process the computed data can be interpreted by any Qanary component. Note that all information stored in G i is retrievable by each Qanary component. Hence, no restrictions w.r.t. the accessible data are imposed (cf.,

⇤ ⇥ R3 ).
Service Composition All Qanary components implement the same lightweight interface and retrieve/store the data using the qa vocabulary. Hence, the Qanary services can be integrated by combining these components, analogously to the Pipes and Filters [START_REF] Buschmann | Pattern-Oriented Software Architecture -Volume 1: A System of Patterns[END_REF] It already contains the registration to the AdminServer and several other functionalities for rapid engineering. Note: There are no restrictions on the functionality nor the programming language (cf., ⇤ ⇥ R1 ); however, the reference implementation is in Java.

Demonstration As an example, we show how to create a QA pipeline providing the functionality focusing on the engineering tasks. The pipeline is aiming at answering the question "What is the real name of Batman?"5 (cf., QALD question no. 92). It will use a component that already exists in the Qanary ecosystem providing functionality for Named Entity Recognition and Disambiguation (NER/NED), e.g., the Qanary DBpedia Spotlight component (cf., [START_REF] Diefenbach | The Qanary Ecosystem: getting new insights by composing Question Answering pipelines[END_REF]). It will interlink the sub-string "Batman" to the DBpedia resource dbr:Batman. However, additional semantics is required to map the textual question to an interpretable representation. Therefore, we will interactively implement a new component C (using Qanary's Maven archetype) which adds new annotations to the Qanary KB T while analyzing the user's question. C will serve only the purpose to identify the relation dbp:alterEgo (i.e., a DBpedia property) while searching for the sub-string "real name" in the question. The demonstration will finish while creating and executing the QA pipeline using the service composition and showing the result of the question.

Discussion Here, we have demonstrated the main advantage a developers receives while integrating a component in the Qanary ecosystem. A rapid engineering process is provided and a created component can easily be interweaved with the already existing ones. A basic installation of a QA pipeline provided with a user interface called Trill can be found at http://www.wdaqua.eu/qa.

Conclusion

In this paper we presented the component model of the reference implementation of the Qanary framework. Qanary components are easy to implement as it was shown in the paper. However, one of the core features is the option to (re)combine components to QA systems without adopting the component's source code, while still having the full freedom of dedicating a (new) component to a completely new functionality. This new functionality might use data from the Qanary triplestore never used before in this particular combination. Hence, as all features are data-driven, allowing to add new functionality to the whole QA system from a local component independently. Additionally, the component model is language-independent and driven by the power of linked data which enables additional features like polymorph data types included in the inbound data. Our main contribution is a component-based architecture enabling developers to create or re-combine components following a plug-and-play approach. While aiming at an optimal system w.r.t. a given use case (scientific) developers are enabled to rapidly create new/adapted QA systems from the set of Qanary components available. Hence, we are handing the scientific QA community an easy-to-use approach reducing the investments for engineering tasks during typical tasks.

Fig. 1 .

 1 Fig. 1. Qanary Component Model (note that Gi might be equal to Go).

  architecture pattern. The Qanary reference implementation (cf., github.com/WDAqua/Qanary →qanary_pipeline-template) takes advantage of the characteristics of Qanary components. It contains a service registry (AdminServer) which is called automatically during the start-up phase by all components. Hence, all Qanary components are known and can be easily composed (cf.,

⇤ ⇥ R2 ), e.g., the following simple user interfaces are provided to create a QA pipeline using a textual or audio question. There components can easily be activated and combined by drag and drop (define order in QA pipeline): http://www.wdaqua.eu/qanary/startquestionansweringwithtextquestion, http://www.wdaqua.eu/qanary/startquestionansweringwithaudioquestion Service Implementation The implementation of a Qanary component is supported using a Maven archetype (cf., github.com/WDAqua/Qanary → qanary-componentarchetype).

Full description at https://github.com/WDAqua/Qanary/wiki/ICWE-2017-demo

Acknowledgments This project has received funding from the European Union's Horizon 2020 research and innovation program under the Marie Sklodowska-Curie grant agreement No 642795.


Christophe Ducottet

Mohamed Elawady
email: mohamed.elawady@univ-st-etienne.fr

Olivier Alata

Cecile Barat

Philippe Colantoni

Cécile Barat

Multiple Reflection Symmetry Detection via Linear-Directional Kernel Density Estimation

Keywords: Multiple Symmetry, Symmetry Detection, Reflection Symmetry, Kernel Density Estimation, Linear-Directional Data

come   L'archive ouverte pluridisciplinaire

Introduction

Reflection symmetry is a fundamental principle of visual perception to feel the equally distributed weights within foreground objects inside an image. These weights are inspected respect to textural complexity of their shapes, in such non-identical manner to preserve a well-balanced composition between similar objects and their surrounding background [START_REF] Hobbs | The visual experience[END_REF][START_REF] Freeman | The Photographer's Eye: Composition and Design for Better Digital Photos[END_REF][START_REF] Zakia | Photographic Composition: A Visual Guide[END_REF]. Detection of reflection symmetry has a principal intermediate-level role in recent computer vision applications [START_REF] Zhao | Exploring principlesof-art features for image emotion recognition[END_REF][START_REF] Ram | Vehicle detection in aerial images using multiscale structure enhancement and symmetry[END_REF][START_REF] Yuan | An incremental framework for video-based traffic sign detection, tracking, and recognition[END_REF][START_REF] Abdolali | Automatic segmentation of maxillofacial cysts in cone beam ct images[END_REF]. Liu et al. [START_REF] Liu | Computational symmetry in computer vision and computer graphics[END_REF] described the global symmetry as top-tier visual features, which are distributed uniformly across the image sides and contributed to define an uppermost similarity behavior. This paper focuses on detecting multiple bilateral symmetry axes by exploring the geometrical correlation between regions on a global scale.

The baseline algorithm was proposed in 2006 by Loy and Eklundh [START_REF] Loy | Detecting symmetry and symmetric constellations of features[END_REF]. They analyzed the bilateral symmetry from image features' constellation by introducing the general scheme: (1) detection of local feature points (i.e. SIFT), associated with local geometrical properties (location, orientation, scale) and descriptor vectors. [START_REF] Akaike | An approximation to the density function[END_REF] pairwise matching and evaluation of a local symmetry magnitude of their descriptors, to generate symmetry candidates. (3) accumulation of their symmetry magnitude in a Hough-like voting space parametrized with orientation and displacement, to identify the dominant reflection axes inside an image. The first survey of symmetry detection algorithms was introduced by the computer vision group of Pennsylvania State University in 2008 [START_REF] Park | Performance evaluation of state-of-the-art discrete symmetry detection algorithms[END_REF]. The same group conducted symmetry detection challenges in 2011 [START_REF] Rauschert | First symmetry detection competition: Summary and results[END_REF] and 2013 [START_REF] Liu | Symmetry detection from realworld images competition 2013: Summary and results[END_REF], where the baseline algorithm [START_REF] Loy | Detecting symmetry and symmetric constellations of features[END_REF] still outperformed the participated approaches [START_REF] Mo | Detecting bilateral symmetry with feature mirroring[END_REF][START_REF] Kondra | Multi-scale kernel operators for reflection and rotation symmetry: further achievements[END_REF][START_REF] Michaelsen | Recognition of symmetry structure by use of gestalt algebra[END_REF][START_REF] Patraucean | Detection of mirror-symmetric image patches[END_REF]. Other keypoint-based algorithms [START_REF] Cho | Bilateral symmetry detection via symmetry-growing[END_REF][START_REF] Cai | An adaptive symmetry detection algorithm based on local features[END_REF] also proposed feature refinement techniques for better results. Edge/contour-based features [START_REF] Ming | Symmetry detection via contour grouping[END_REF][START_REF] Cicconet | Mirror symmetry histograms for capturing geometric properties in images[END_REF][START_REF] Wang | Reflection symmetry detection using locally affine invariant edge correspondence[END_REF][START_REF] Atadjanov | Bilateral symmetry detection based on scale invariant structure feature[END_REF][START_REF] Cicconet | A convolutional approach to reflection symmetry[END_REF][START_REF] Atadjanov | Reflection symmetry detection via appearance of structure descriptor[END_REF][START_REF] Elawady | Global bilateral symmetry detection using multiscale mirror histograms[END_REF] are modernly used instead of the intensity-based, due to saliency properties in detecting well-defined symmetric structures inside an object. In both approaches, a limited number of feature points are detected in the image, axis candidates are randomly sampled across the voting space. These sparse symmetry candidates further need to be grouped through a smoothing kernel to define relevant monoor multi-axis hypothesis. Our idea is to formulate the voting problem as a density estimation problem, by computing the probability of detecting symmetry axis at every position and orientation inside the image plane.

Kernel density estimation is one of the most popular techniques in nonparametric statistics. Density estimates are controlled by a smoothing bandwidth and a weighting kernel function. Density estimates with linear kernels have been introduced in 1954 [START_REF] Akaike | An approximation to the density function[END_REF], and then have been adapted to deal with directional data since the mid 1980s [START_REF] Hall | Kernel density estimation with spherical data[END_REF]. Many computer vision applications used kernel density estimation for linear data [START_REF] Elgammal | Background and foreground modeling using nonparametric kernel density estimation for visual surveillance[END_REF][START_REF] Mittal | Motion-based background subtraction using adaptive kernel density estimation[END_REF][START_REF] Zhang | Applying neighborhood consistency for fast clustering and kernel density estimation[END_REF][START_REF] Cremers | Kernel density estimation and intrinsic alignment for shape priors in level set segmentation[END_REF][START_REF] Van Gemert | Kernel codebooks for scene categorization[END_REF][START_REF] Wang | Semisupervised kernel density estimation for video annotation[END_REF][START_REF] Tavakoli | Fast and efficient saliency detection using sparse sampling and kernel density estimation[END_REF][START_REF] Liu | Unsupervised salient object segmentation based on kernel density estimation and two-phase graph cut[END_REF], and fewer recently used it for directional data [START_REF] Vuollo | Analyzing infant head flatness and asymmetry using kernel density estimation of directional surface data from a craniofacial 3d model[END_REF][START_REF] Pardo | Directional kernel density estimation for classification of breast tissue spectra[END_REF]. Garcia-Portugues et al. [START_REF] García-Portugués | Kernel density estimation for directional-linear data[END_REF] derived the general principle of joint kernel density estimator for linear-directional data.

Our contribution is twofold. First we propose a weighted joint density estimator to handle both orientation and displacement information. Second, we introduce a robust linear-directional kernel-based voting representation for reflection symmetry detection. This approach is evaluated for multiple symmetry detection using two public datasets. The remaining sections of this paper are organized as follows. Section 2 describes the proposed algorithm. Sections 3 and 4 present the experimental details and results on two public datasets. Finally, the conclusion is given in section 5.

Algorithm Details

Given an image, our algorithm focuses globally to detect all symmetry axes using a dense and regular estimation of linear-directional density, as briefly shown in figure 1. First, we extract wavelet-based features with different scales, accompanied with edge and textural characteristics (for better display, only features with high magnitude are displayed over the gray-scale version of the input image). Second, we triangulate each feature pair at each scale with respect to the origin of the feature space, in order to define symmetrical weights in the polar coordinate system. Third, we formulate a voting representation based on weighted pairs via linear-directional kernel density estimation. Finally, the global symmetry axes are well-chosen by searching for maximum peaks, and spatially defined by the convex hull of the voting features. Fig. 1: The proposed framework of reflection symmetry detection, using a weighted linear-directional kernel density estimator (LD-KDE). Best seen on screen (zoom-in for details).

Feature Extraction and Normalization

Upon the application of Morlet wavelet over an image with multiple scales, feature points {p i = [p i x , p i y ] T , i = 1 . . . P } are sampled, as detailed in [START_REF] Elawady | Global bilateral symmetry detection using multiscale mirror histograms[END_REF], along a regular grid with respect to image size (width W and height H), along side with their local edge components (scale σ i , maximum wavelet response J i and direction τ i over all orientations) plus neighboring textural histograms h i . These points are normalized with keeping aspect ratio as following:

pi = p i -c W,H max(W, H) (1)
where c W,H represents the original image center ( W 2 , H 2 ). So that, the feature space is transferred from the dynamic-sized image plane [

1, W ] × [1, H] to a unified version [-1, 1] × [-1, 1].

Pairwise Symmetry Triangulation

We first define a set of feature pairs {q n = (p i , pj ) | n = 1, . . . , N } such that i = j and σ i = σ j . Then, we perform a triangulation process (as illustrated in Fig. 2: Symmetric triangulation for a feature pair. Best seen on screen.

figure 2) with respect to the feature origin, producing the symmetry candidate axis as the bisector of the pair segment. The candiate axis is parametrized by angle θ n ∈ [0, π], and displacement

ρ n ∈ [- √ 2 2 , √ 2
2 ]) and has a symmetry weight ω n [START_REF] Cicconet | Mirror symmetry histograms for capturing geometric properties in images[END_REF][START_REF] Elawady | Global bilateral symmetry detection using multiscale mirror histograms[END_REF] defined as follows:

ω n = m n c n d n , ||ω|| 1 = 1 (2)
where m n ∈ [0, 1] is a semi-dense edge magnitude, c n ∈ [0, 1] is a mirror symmetry coefficient based on the local edge orientation of points of the pair,

d n ∈ [0, 1]
is a measure based on histograms h i and h j , representing the similarity between the local texture around the feature points, and ||.|| 1 is L 1 norm.

Weighted Linear-Directional Kernel Density Estimation

One dimensional linear variable ρ represents displacement part of a candidate axis, assuming ρ 1 , . . . , ρ N samples of ρ with size N . Let µ describes two dimensional directional variable (circular data corresponds to angle θ, representing orientation part of a candidate axis, see figure 2), assuming µ 1 , . . . , µ N samples of µ with the same size of ρ. Inspired from [START_REF] Parzen | On estimation of a probability density function and mode[END_REF], the linear kernel density estimator f l (.) is defined as

f l (x; g) = 1 N g N n=1 G( x -ρ n g ), x ∈ R (3)
G(u) = 1 (2π) 1 2 e -1 2 |u| 2 , (4)
where G(.) is a Gaussian kernel with bandwidth parameter g. Inspired from [START_REF] Hall | Kernel density estimation with spherical data[END_REF], the directional kernel density estimator f d (.) is defined as:

f d (y; k) = C(k) N n=1 L(y T µ n ; k), y ∈ Ω 2 (5) L(x; k) = e kx , C(k) = 1 2πS(0, k) , (6)
y = [cos(θ), sin(θ)], µ n = [cos(θ n ), sin(θ n )], (7)
where L(.) is a von-Mises Fisher kernel [START_REF] Mardia | Directional statistics[END_REF] with concentration parameter k, and normalization constant C(k). S(.) is the modified Bessel function of the first kind. y is remarked as directional unit-vector of angle θ, such that ||y|| = 1.

As axis candidate samples (ρ 1 , µ 1 ), . . . , (ρ N , µ N ) are associated with symmetry weights ω 1 , ω 2 , • • • , ω N , and use of the linear-directional density estimator f l,d (.) in [START_REF] García-Portugués | Kernel density estimation for directional-linear data[END_REF]. We define the extended weighted version fl,d (.) as:

fl,d (x, y; g, k) = C(k) N g N n=1 ω n G( x -ρ n g )L(y T µ n ; k) (8)
assuming that linear and directional data are independent resulting dot product between accompanying kernels. Previous weights (see equation 2) are multiplied by N in order to normalize fl,d .

The multiple symmetry peaks inside the voting representation fl,d (.) are identified through finding non-interleaved extreme spots via a standard non-maximal suppression technique [START_REF] Canny | A computational approach to edge detection[END_REF]. The spatial extent of each peak representing a symmetry axis is determined by the convex hull of the voting pair associated with the peak [START_REF] Loy | Detecting symmetry and symmetric constellations of features[END_REF]. Figures [3a-3d] present an example of multiple symmetry detection, using 1D and 2D kernel-based voting maps. Three vertical symmetry axes are shown in the weighted linear kernel density fl (x; g) (figure 3b). Two major directional axes appear in the weighted directional kernel density fd (y; k) at angles θ = 90 • , 180 • (figure 3c). All global symmetry axes are clearly recognized through the combination version of the previous weighted densities fl,d (x, y; g, k) (figure 3d). To obtain such representation, as θ originally belongs to [0, π), each angle value is multiplied by 2 in order to obtain an appropriate periodicity with the directional kernel.

Implementation and Evaluation Details

We compare our reflection symmetry detection approach against three different methods (Loy2006 [START_REF] Loy | Detecting symmetry and symmetric constellations of features[END_REF], Cicconet2014 [START_REF] Cicconet | Mirror symmetry histograms for capturing geometric properties in images[END_REF], and Elawady2016 [START_REF] Elawady | Global bilateral symmetry detection using multiscale mirror histograms[END_REF]). We executed their source codes with default parameter values, assigned by the authors for stable performance. For our approach, we empirically set the linear-kernel bandwidth parameter g to 0.03, and directional-kernel concentration parameter k to 40. Two public datasets are used to represent multiple reflection symmetry detection results: (1) PSU dataset: Liu's vision group proposed a symmetry groundtruth for Flickr images (# images = 142, # symmetries = 479) in ECCV2010 1 , CVPR2011 2 and CVPR2013 3 . Non-duplicative images are com- bined from three previously mentioned versions for challenging comparisons. (2) NY dataset: Cicconet et al. [START_REF] Cicconet | A convolutional approach to reflection symmetry[END_REF] presented a new symmetry database (# images = 63, # symmetries = 188) in 2016 4 , providing more accurate and consistent groundtruth for multiple symmetry endpoints. Quantitative comparisons are performed as proposed in [START_REF] Rauschert | First symmetry detection competition: Summary and results[END_REF][START_REF] Liu | Symmetry detection from realworld images competition 2013: Summary and results[END_REF], where a detected symmetry axis considered as a true positive (TP): 1) The angle between the detected symmetry axis and its corresponding groundtruth symmetry axis is less than 10 degree; 2) The distance between the centers of detected and same groundtruth axes is less than 20% minimum length of the axes. Multiple detections can match to the same ground-truth axis, but not vice versa. The overall performance of algorithms are defined through the precision and recall rates:

precision = T P T P + F P , recall = T P T P + F N . (9)
where false positive (FP) are non-matched detected axes with any groundtruth, false negative (FN) are non-matched groundtruth with any detected axes. Close detections are clustered as one proposal axis to avoid duplicates in true positive or false positive calculations.

Experiments and Discussions

Quantitative (figures 4, 5) and qualitative (figure 6) comparisons are conducted among the proposed method (Our2017), Loy and Eklundh [START_REF] Loy | Detecting symmetry and symmetric constellations of features[END_REF]) [START_REF] Loy | Detecting symmetry and symmetric constellations of features[END_REF], Cicconet et al. (Cic2014) [START_REF] Cicconet | Mirror symmetry histograms for capturing geometric properties in images[END_REF], and Elawady et al. (Ela2016) [START_REF] Elawady | Global bilateral symmetry detection using multiscale mirror histograms[END_REF]. Loy2006 and Ela2016 were reported to have the best performed results for the single symmetry detection in keypoint-based and edge-based methods respectively [START_REF] Elawady | Global bilateral symmetry detection using multiscale mirror histograms[END_REF]. Figure 4 presents precision-recall curves for the multiple symmetry datasets (PSUm [START_REF] Rauschert | First symmetry detection competition: Summary and results[END_REF][START_REF] Liu | Symmetry detection from realworld images competition 2013: Summary and results[END_REF], and NYm [START_REF] Cicconet | A convolutional approach to reflection symmetry[END_REF]), to compare the proposed method to three prior algorithms (Loy2006 [START_REF] Loy | Detecting symmetry and symmetric constellations of features[END_REF], Cic2014 [START_REF] Cicconet | Mirror symmetry histograms for capturing geometric properties in images[END_REF], and Ela2016 [START_REF] Elawady | Global bilateral symmetry detection using multiscale mirror histograms[END_REF]). Cic2014 [START_REF] Cicconet | Mirror symmetry histograms for capturing geometric properties in images[END_REF] has the lowest performance for precision and recall in both curves. In figure 4a, Loy2006 [START_REF] Loy | Detecting symmetry and symmetric constellations of features[END_REF] has better precision than Ela2016 [START_REF] Elawady | Global bilateral symmetry detection using multiscale mirror histograms[END_REF] over corresponding low recall, while the precision of the proposed method (aka Our2017) outperforms all these methods in most sections of the curve. In figure 4b, Ela2016 [START_REF] Elawady | Global bilateral symmetry detection using multiscale mirror histograms[END_REF] has a superior precision performance over Loy2006 [START_REF] Loy | Detecting symmetry and symmetric constellations of features[END_REF] under the recall rate of 40%, meanwhile the proposed method has the best performance along both precision and recall rates. Additionally, we also compute the F 1 score to define the harmonic mean between precision and recall rates, and used the maximum F 1 score to qualify the overall performance of different detection algorithms. The values of maximum F 1 score are presented in figure 4 to express the precision-recall curve for each method in a single global measure. Figure 5 shows precision and recall rates where the maximum F 1 scores are selected among the corresponding curves in figure 4.

The proposed method achieved the best performance among all results. Figure 6 presents some experimental results for multiple symmetry detection from two publicly available datasets (PSUm [START_REF] Rauschert | First symmetry detection competition: Summary and results[END_REF][START_REF] Liu | Symmetry detection from realworld images competition 2013: Summary and results[END_REF], NYm [START_REF] Cicconet | A convolutional approach to reflection symmetry[END_REF]). Groundtruth of [START_REF] Rauschert | First symmetry detection competition: Summary and results[END_REF][START_REF] Liu | Symmetry detection from realworld images competition 2013: Summary and results[END_REF] and (b)NYm [START_REF] Cicconet | A convolutional approach to reflection symmetry[END_REF] datasets to show the superior performance of our method "Our2017" against the three prior algorithms ("Loy2006" [START_REF] Loy | Detecting symmetry and symmetric constellations of features[END_REF], "Cic2014" [START_REF] Cicconet | Mirror symmetry histograms for capturing geometric properties in images[END_REF], "Ela2016" [START_REF] Elawady | Global bilateral symmetry detection using multiscale mirror histograms[END_REF]). The maximum F1 scores are qualitatively presented as square symbols along the curves, and quantitatively indicated between parentheses inside the top-right legends. Best seen on screen. Fig. 5: Comparison of maximum F1 score and its equivalent precision and recall rates among two different dataset (PSUm [START_REF] Rauschert | First symmetry detection competition: Summary and results[END_REF][START_REF] Liu | Symmetry detection from realworld images competition 2013: Summary and results[END_REF], NYm [START_REF] Cicconet | A convolutional approach to reflection symmetry[END_REF]) for our method "Our2017" against the baseline algorithm "Loy2006" [START_REF] Loy | Detecting symmetry and symmetric constellations of features[END_REF] and two of the recent algorithms "Cic2014" [START_REF] Cicconet | Mirror symmetry histograms for capturing geometric properties in images[END_REF] and "Ela2016" [START_REF] Elawady | Global bilateral symmetry detection using multiscale mirror histograms[END_REF]. Fig. 6: Some challenging images in PSUm [START_REF] Rauschert | First symmetry detection competition: Summary and results[END_REF][START_REF] Liu | Symmetry detection from realworld images competition 2013: Summary and results[END_REF] (1st and 2nd columns) and NYm [START_REF] Cicconet | A convolutional approach to reflection symmetry[END_REF] (3rd column) datasets with groundtruth in 1st row (a,b,c). our method in 2nd row (d,e,f) produces better results among El2016 [START_REF] Elawady | Global bilateral symmetry detection using multiscale mirror histograms[END_REF] in 3rd row (g,h,i) and Loy2006 [START_REF] Loy | Detecting symmetry and symmetric constellations of features[END_REF] in 4th row (j,k,l). For each algorithm, the top five symmetry results is presented in such order: red, yellow, green, blue, and magenta. Each symmetry axis is shown in a straight line with squared endpoints. Best seen on screen.

the first example (figure 6a) shows four symmetries (vertical, horizontal, and diagonals) of a flower within natural background view. The proposed method (figure 6d) detects correctly vertical and horizontal axes, while Loy2006 [START_REF] Loy | Detecting symmetry and symmetric constellations of features[END_REF] (figure 6j) fails to find enough feature points resulting two partial (diagonal and vertical) axes, and Ela2016 [START_REF] Elawady | Global bilateral symmetry detection using multiscale mirror histograms[END_REF] (figure 6g) breakdown the vertical axis to represent the top five detections. Second and third examples (figures 6b, 6c) display three in-between symmetries of a thinned metal object and five symmetries expressing arms' details of a starfish respectively over variant texture-less surfaces. These symmetries have been efficiently detected by the proposed method (figures 6e, 6f) over Ela2016 [START_REF] Elawady | Global bilateral symmetry detection using multiscale mirror histograms[END_REF] (figures 6h, 6i). However, Loy2006 [START_REF] Loy | Detecting symmetry and symmetric constellations of features[END_REF] (figures 6k, 6l) concentrates on local symmetries describing the inner details of the centric objects.

Conclusion

This paper proposes a linear-directional kernel-based voting scheme within unified feature representation, in order to support a reliable detection framework for global multiple symmetries. Our approach solves the drawbacks of the previous symmetry detection approaches, by estimating the fixed-sized kernel density with efficient bandwidth parameters, and identifying correctly the symmetrical regions at a global scale. Quantitative and qualitative evaluations present the state-of-the-art performance of our proposed framework among public datasets. This work can be extended to refine the accuracy of the symmetry peaks and the selection of corresponding voting features, using a continuous maxima-seeking technique. The future work is introducing an entropy-based measure, to exploit the global strength of various symmetry axes inside an image.

1Fig. 3 :

 3 Fig. 3: Symmetry detection process: (a) Input image with global symmetry axis candidates. (b) The output of weighted linear kernel density fl (x; g) over 800 bins. (c) The output of the weighted directional kernel density fd (y; k) over 180 bins. (d) The output of the weighted linear-directional kernel density fl,d (x, y; g, k) over 800 × 180 bins. Maximal peaks are associated with global symmetry axes. Best seen on screen.

Fig. 4 :

 4 Fig.4: Precision-Recall curves on (a)PSUm[START_REF] Rauschert | First symmetry detection competition: Summary and results[END_REF][START_REF] Liu | Symmetry detection from realworld images competition 2013: Summary and results[END_REF] and (b)NYm[START_REF] Cicconet | A convolutional approach to reflection symmetry[END_REF] datasets to show the superior performance of our method "Our2017" against the three prior algorithms ("Loy2006"[START_REF] Loy | Detecting symmetry and symmetric constellations of features[END_REF], "Cic2014"[START_REF] Cicconet | Mirror symmetry histograms for capturing geometric properties in images[END_REF], "Ela2016"[START_REF] Elawady | Global bilateral symmetry detection using multiscale mirror histograms[END_REF]). The maximum F1 scores are qualitatively presented as square symbols along the curves, and quantitatively indicated between parentheses inside the top-right legends. Best seen on screen.

  (a) ref rm 79 -GT (b) ref rm 71 -GT (c) I012 -GT (d) ref rm 79 -Our2017 (e) ref rm 71 -Our2017 (f) I012 -Our2017 (g) ref rm 79 -Ela2016 (h) ref rm 71 -Ela2016 (i) I012 -Ela2016 (j) ref rm 79 -Loy2006 (k) ref rm 71 -Loy2006 (l) I012 -Loy2006

http://symmetry.cs.nyu.edu/