Valentina Ivanova

Benjamin Bach

Emmanuel Pietriga

Patrick Lambrix

Alignment Cubes: Towards Interactive Visual Exploration and Evaluation of Multiple Ontology Alignments

Keywords: Ontology alignment evaluation, Visual exploration, Multiple alignment comparison

Ontology alignment is an area of active research where many algorithms and approaches are being developed. Their performance is usually evaluated by comparing the produced alignments to a reference alignment in terms of precision, recall and F-measure. These measures, however, only provide an overall assessment of the quality of the alignments, but do not reveal differences and commonalities between alignments at a finer-grained level such as, e.g., regions or individual mappings. Furthermore, reference alignments are often unavailable, which makes the comparative exploration of alignments at different levels of granularity even more important. Making such comparisons efficient calls for a "human-in-the-loop" approach, best supported through interactive visual representations of alignments. Our approach extends a recent tool, Matrix Cubes, used for visualizing dense dynamic networks. We first identify use cases for ontology alignment evaluation that can benefit from interactive visualization, and then detail how our Alignment Cubes support interactive exploration of multiple ontology alignments. We demonstrate the usefulness of Alignment Cubes by describing visual exploration scenarios, showing how alignment cubes support common tasks identified in the use cases.

Introduction

The need for automatic alignment of ontologies has sparked the development of a growing number of tools and algorithms. A comprehensive literature review can be found in [START_REF] Otero-Cerdeira | Ontology matching: A literature review[END_REF]. It has also led to the creation of an annual event, the Ontology Alignment Evaluation Initiative (OAEI) 4 , where alignments computed by the participating tools are compared against reference alignments (RA). In most cases the quality of these alignments is measured in terms of precision, recall, and F-measure. Precision is the ratio of correct suggested mappings over all suggested mappings. Recall is the ratio of correct suggested mappings over all correct mappings. F-measure is a harmonic mean between precision and recall. These measures give a good overall assessment of the quality of alignments in terms of the ratio of found mappings, missed mappings and wrongly suggested mappings. However, they do not allow for comparing alignments of specific parts of ontologies, or for comparing alignments to each other and to the RA at the detailed level of concepts and relations. Without means to compare the tools and algorithms at a detailed level, their strengths and weaknesses cannot be easily revealed and understood.

Furthermore, RAs are often not available, as their development is time and effort consuming and requires domain expertise. As a consequence, the quality of alignments is difficult to measure. In the absence of RA, the evaluation of alignments requires the exploration and comparison of multiple alignments, which involves expert users (analysts) performing tasks at different levels of granularity [START_REF] Aurisano | Visual analytics for ontology matching using multilinked views[END_REF][START_REF] Dragisic | Experiences from the anatomy track in the ontology alignment evaluation initiative[END_REF][START_REF] Severo | A gui for visualising and manipulating multiple ontology alignments[END_REF]: determining regions with similar or different numbers of mappings between the alignments, determining common or rarely found mappings, characterizing mappings as correct or incorrect. However, there is currently little support for performing these tasks in an interactive and flexible manner. Analysts are relying on custom scripts, which can be error-prone and require time to develop and fine-tune.

In this paper, we propose an interactive visualization interface for the simultaneous comparative exploration and evaluation of multiple alignments at different levels of granularity. While visualizing even a single alignment is still a challenge due to the size and complexity of the ontologies, we provide a way to visualize multiple alignments. Instead of depicting all mappings together in a single representation, which would cause visual clutter and information overload, we provide an interactive visualization that supports multiple complementary views, and overview and detail techniques to explore alignments at different levels of granularity. We interpret an alignment as a bipartite graph (bi-graph), i.e., a network where links exist only between nodes of different sets (ontologies), and draw from the literature in the field of network visualization (e.g., [START_REF] Von Landesberger | Visual analysis of large graphs: state-of-the-art and future research challenges[END_REF][START_REF] Beck | The state of the art in visualizing dynamic graphs[END_REF]). To that end, we extend and adapt a technique introduced for the interactive visual exploration of dynamic networks, called Matrix Cubes [START_REF] Bach | Visualizing dynamic networks with matrix cubes[END_REF]. Our visualization, called Alignment Cubes, extends Matrix Cubes in several ways, so as to make it applicable to the visualization of multi-level ontology alignment networks in the form of bi-graphs.

This article is structured as follows: Section 2 presents use cases requiring analyses of multiple alignments, identifies features for our visualization tool, and discusses existing approaches for visualizing multiple alignments. Section 3 describes Matrix Cubes, and Section 4 describes the Alignment Cubes we derived from them. We explain how users interact with Alignment Cubes using an example scenario in Section 5, discuss lessons learned and future extensions in Section 6, and conclude in Section 7.

Ontology Alignment Evaluation

The interactive exploration and evaluation of several alignments is only rarely considered in the literature. In [START_REF] Aurisano | Visual analytics for ontology matching using multilinked views[END_REF] several analytic tasks have been identified and supported through multiple connected views, while [START_REF] Lambrix | A tool for evaluating ontology alignment strategies[END_REF][START_REF] Peukert | Amc-a framework for modeling and comparing matching systems as matching processes[END_REF][START_REF] Severo | A gui for visualising and manipulating multiple ontology alignments[END_REF] focus more on the alignment computation than their presentation. We thus first identify several evaluation use cases and discuss shared activities that could be efficiently supported through interactive visualization in Subsection 2.1. In Subsection 2.2 we connect this discussion with work about cognitive support for ontology mapping [START_REF] Falconer | A Cognitive Support Framework for Ontology Mapping[END_REF], requirements and evaluation of user interfaces in ontology alignment systems [START_REF] Ivanova | Requirements for and evaluation of user support for large-scale ontology alignment[END_REF][START_REF] Dragisic | User validation in ontology alignment[END_REF], and review capabilities for simultaneous visualization of several alignments in existing systems. In Subsection 2.3, we study the visualization approaches taken in alignment evaluation frameworks.

Evaluation Use Cases

The following use cases would benefit from users being able to simultaneously explore and evaluate several alignments interactively: (UC1) Selecting, combining and fine tuning alignment algorithms and tools: OAEI editions, and [START_REF] Shvaiko | Ontology Matching: State of the Art and Future Challenges[END_REF][START_REF] Dragisic | Experiences from the anatomy track in the ontology alignment evaluation initiative[END_REF] among others, have shown that matchers and tools do not necessarily find the same correct mappings, and may compute different erroneous mappings too. Thus, selecting and combining matchers and tools requires examination of overlapping and divergent mappings to understand the differences in the underlying algorithms. It also includes assessing the impact of parameter changes on single similarity values and parts of the alignments for fine-tuning. (UC2) Matchers development: Developers alter their algorithms according to some observations. Examining the outcome of such changes over other parts of the alignment and comparing to previous versions at different levels of granularity helps them assess the consequences of these changes. (UC3) Ontology alignment evolution: Alignments are used for, e.g., data integration, merging ontologies, and database annotation. Changes in the alignments may influence the applications employing them. Understanding how alignments differ will facilitate the assessment of the impact of changes on their client applications [START_REF] Lambrix | Visualization for ontology evolution[END_REF][START_REF] Zablith | Ontology evolution: a process-centric survey[END_REF]. (UC4) Validating and debugging of ontology alignments and RA: Analyzing several alignments at the same time may reveal parts with large variations in the number of mappings or similarity values, and help in identifying potential errors and their sources during diagnosis. Developing and debugging RAs is a laborious and errorprone task. Recently, several works have found problems in the OAEI Anatomy track's RA [START_REF] Dragisic | Experiences from the anatomy track in the ontology alignment evaluation initiative[END_REF]. Manual mapping validation requires a detailed view of each mapping and its context [START_REF] Falconer | A Cognitive Support Framework for Ontology Mapping[END_REF]. Understanding consequences of user validations and exploring what-if scenarios are also important [START_REF] Ivanova | Requirements for and evaluation of user support for large-scale ontology alignment[END_REF]. (UC5) Collaborative ontology alignment: Collaborators need to understand the current state of an alignment, where and why their peers have introduced changes in comparison to previous revisions. This is especially needed when collaborative work happens over a long time period, or in distributed teams.

These use cases share common analytic tasks at different granularity levels; identifying parts of the alignment covered or not covered by all alignments, agreement or disagreement between matchers, determining incorrect, missed or always found mappingswhich could be efficiently supported through interactive visualizations. Without measures to provide well-defined quantitative outputs, and with only high-level goals and questions, e.g., which threshold to choose and why (UC1), which version of my algorithm is better and why (UC2), what has been changed between two revisions and why (UC3,UC5), all of the use cases above are exploratory in their nature. They aim to find relevant information and answer questions not known in advance.

They are typical scenarios in which visual and interactive representations can be of help. In a visual environment exploration activities are supported by interactively varying parameters and thresholds to estimate the impact of changes, changing visual encodings to highlight different aspects, and reordering elements to facilitate trend and pattern discovery. Interactive exploration at different granularity levels reveals regions of interest to guide further exploration and help in identifying patterns in and among different regions of interest which may reveal similarities and dissimilarities between the respective alignments. These benefits directly apply to our case, where analysts are faced with the problem of exploring and visualizing multiple alignments.

Our use cases UC1-UC5 involve numerous compare and contrast tasks to select a threshold (UC1), an alignment to use (UC2 and UC4), for diagnosis and to identify outliers (UC4), common trends and regions (UC1, UC2), and for identifying changes (UC3, UC5). According to [START_REF] Aurisano | Visual analytics for ontology matching using multilinked views[END_REF], diagnosis is a complex activity which is composed of iterative sequences of exploration and comparison, analyses of clusters of mappings, and comparative evaluation of matcher performance.

Existing Approaches

Two recent studies review exploratory features in the user interfaces of ontology alignment systems [START_REF] Ivanova | Requirements for and evaluation of user support for large-scale ontology alignment[END_REF][START_REF] Dragisic | User validation in ontology alignment[END_REF]. Only one of the tools [START_REF] Cruz | Interactive user feedback in ontology matching using signature vectors[END_REF] (including its recent extensions [START_REF] Aurisano | Visual analytics for ontology matching using multilinked views[END_REF][START_REF] Li | Interactive visualization of large ontology matching results[END_REF]) provides support for visualization and exploration of several alignments together after discussing the need for such in connection to analytic tasks identified in interviews with alignment experts. Navigation and exploration in ontologies and just a single alignment have been highlighted in the context of discovering mappings and verification in [START_REF] Falconer | A Cognitive Support Framework for Ontology Mapping[END_REF], through the inspection dimension defined in [START_REF] Ivanova | Requirements for and evaluation of user support for large-scale ontology alignment[END_REF], and by the 7 information seeking tasks and visual analytics from [START_REF] Dragisic | User validation in ontology alignment[END_REF]. Another desirable functionality identified by alignment experts in [START_REF] Aurisano | Visual analytics for ontology matching using multilinked views[END_REF] is the clustering of mappings according to different statistics in order to analyze each cluster separately. Several other works have also emphasized the importance of visually identifying dense regions in single alignments: for planning manual validation and identifying the most similar areas of the ontologies [START_REF] Falconer | A Cognitive Support Framework for Ontology Mapping[END_REF], as part of alignment inspection [START_REF] Ivanova | Requirements for and evaluation of user support for large-scale ontology alignment[END_REF], and grouping to help identifying patterns [START_REF] Dragisic | User validation in ontology alignment[END_REF]. Small-world graphs were used to present clusters in a single alignment at different granularity levels [START_REF] Lanzenberger | Ontology visualization: Tools and techniques for visual representation of semi-structured meta-data[END_REF].

The exploration and comparison task functionality identified by experts in [START_REF] Aurisano | Visual analytics for ontology matching using multilinked views[END_REF], is supported through comparative views by showing juxtaposed matrices computed by a combination of different matchers in the system. An additional matrix highlights variations in computed mappings between the matchers. RAs can be overlaid on top of each matcher's matrix. This approach is similar to one of the views in our approach using Matrix Cubes [START_REF] Bach | Visualizing dynamic networks with matrix cubes[END_REF]-small multiples-but in comparison to our work, it forgoes the structure of the ontologies which is shown in another view. Similar to our approach, previous work [START_REF] Dang | Provenancematrix: A visualization tool for multi-taxonomy alignments[END_REF][START_REF] El | imerge: interactive ontology merging[END_REF] has presented the structure of ontologies as indented trees on the sides of a matrix, but only focused on a single alignment. One of them [START_REF] Dang | Provenancematrix: A visualization tool for multi-taxonomy alignments[END_REF] provides support for reordering and depicts several types of mappings as well as derived and asserted mappings. Recent work [START_REF] Severo | A gui for visualising and manipulating multiple ontology alignments[END_REF] takes another approach to simultaneously visualizing several (externally-generated) alignments, employing linked indented lists and color-coding to depict the edges belonging to different alignments. The authors emphasize that with their tool "[...] users can better compare and analyze alignments (i.e., parts of the ontologies which are covered for most alignments and those which are not, consensus between alignments, etc.)". Although filtering by threshold and mapping type is supported, the view quickly becomes cluttered as the size of ontologies and the number of alignments involved grow.

Frameworks for Ontology Alignment Evaluation

A few ontology alignment evaluation frameworks, SEALS 5 , KitAMO [START_REF] Lambrix | A tool for evaluating ontology alignment strategies[END_REF] and AMC [START_REF] Peukert | Amc-a framework for modeling and comparing matching systems as matching processes[END_REF], provide rich back-end infrastructures for configuring (to a different extent), executing and storing the results from the execution of alignment components (matchers, filters and combination algorithms). In SEALS, used in OAEI, the alignments computed by the tools are compared to RA and evaluated in terms of precision, recall, F-measure, run time, coherence and number of requests to an oracle. The results are presented in sortable tables, after analysis with custom scripts. In KitAMO [START_REF] Lambrix | A tool for evaluating ontology alignment strategies[END_REF], probably the earliest system, the results are presented in the form of sortable tables containing either the mappings with their similarity values computed by each component, or aggregated data (number of correct, incorrect and inferred mappings) in comparison to another component. In AMC [START_REF] Peukert | Amc-a framework for modeling and comparing matching systems as matching processes[END_REF], linked indented lists are used together with sortable tables as well. It additionally introduces a cube view which presents a single alignment where two of the dimensions depict the source and target ontologies, and the third dimension shows similarity values as bars-taller bars representing higher similarity values.

While all three frameworks provide rich back-end infrastructures for configuring and executing alignment algorithms, the tabular views are too limited to adequately address the simultaneous interactive comparison of several alignments and provide visual exploration at different granularity levels. The third framework devotes more attention to the visual presentation of the results, but it only depicts one alignment at a time. In comparison, our work focuses on the user interface and allows users to visually explore multiple alignments together. It can thus be seen as complementary to the back-end functionalities offered by these frameworks.

Matrix Cubes and the Cubix Interface

Alignment Cubes are adapted from earlier work that introduced Matrix Cubes [2] as an interactive visualization metaphor for the comparison of multiple time steps in dynamic networks. Here, we briefly summarize Matrix Cubes and Cubix, the interactive interface prototype used to manipulate and explore Matrix Cubes, and refer readers to [START_REF] Bach | Visualizing dynamic networks with matrix cubes[END_REF].

Dynamic networks are networks whose topology and attributes change over time. The general idea of Matrix Cubes is to represent the different states (time steps) of a dynamic network as adjacency matrices, one matrix showing the state of the network at one given point in time. Each adjacency matrix is organized as follows (fig. 1-a cell at the intersection of a given row and column will only be filled if there is a link between the two corresponding nodes. Attributes of such links can be encoded visually inside the matrix cells', using variables such as, e.g., color hue or saturation, texture, and glyph size. All adjacency matrices corresponding to the individual states of the network over time are then stacked, forming a cube (fig. 1-b). The resulting 3D visualization acts mainly as a pivot and metaphor. Users manipulate the cube interactively to derive multiple meaningful 2D projections of the cube or its content, better suited to their visual analysis tasks. Manipulations include slicing the cube along different dimensions, rotating slices or the entire cube, juxtaposing slices to obtain small-multiple views, playing with cells' transparency to enable detailed compare & contrast tasks between slices.

As shown in fig. 1-b, Matrix Cubes hold the network's nodes along two of the cube's three dimensions, the last dimension representing time, i.e., the different states of the network over time. As detailed below, instead of representing time on the cube's third dimension, our Alignment Cubes represent the different alignments being compared.

An interactive visualization environment for Matrix Cubes, called Cubix, has been developed in Java + OpenGL by the authors of [START_REF] Bach | Visualizing dynamic networks with matrix cubes[END_REF]. Our prototype Alignment Cube visualization tool is derived from the Cubix implementation. While Matrix Cubes are the general visualization structure (i.e., the 3D cube consisting of matrices) and Cubix is the interactive interface, the term Alignment Cubes refers to both; a specialization of Matrix Cubes and the name of our interface.

Alignment Cubes

This section details our extensions and adaptations of Matrix Cubes for the purpose of ontology alignment evaluation. We describe our tool, Alignment Cubes 6 , in connection to the discussion in Section 2. Fig. 2: Alignment Cube UI. Widgets (sliders, button groups, etc.) mentioned in the text are referred to directly using their name. The cubelet (bottom left corner) is used to switch between views by clicking or dragging the mouse on its faces.

From Matrix Cubes to Alignment Cubes

Two ontologies and their alignment can be seen as a bipartite network of mappings between individual concepts in the two ontologies. A matrix represents a single alignment between two ontologies. The rows hold the concepts from one ontology, the columns hold the concepts from the other ontology. Cells denote existing mappings between concepts in the respective rows and columns. Stacking several matrices, i.e., several alignments, creates an Alignment Cube.

The examples in fig. 2 and3 show two of the ontologies from the OAEI Conference track, ekaw (columns, 77 concepts) and confOf (rows, 38 concepts), as well as seven alignments (laid out along the depth dimension), i.e., the RA for 2016 and alignments from AML and the LogMap-family of systems from 2011 to 2013. Each alignment is color-coded to make it easy to visually differentiate the mappings, by grouping the cells that belong to each of them using a pre-attentive variable. Position is not sufficient to clearly identify which alignment a cell belongs to, as the cube can be manipulated in many ways (rotation, slicing, etc.).

Concepts in ontologies often form a taxonomic hierarchy, but as Matrix Cubes do not support hierarchical networks, we extended the original framework. With Alignment Cubes, we represent the ontologies as indented lists with collapsible rows and columns. Fig. 3-a and b depict the first level in both ontologies. Concepts that feature sub-concepts display the >> symbol after the concept label (e.g., Event, present in both ontologies, features sub-concepts). Clicking on a concept label expands the corresponding row or column. Expanded concepts then show the > symbol, and sub-concepts are indented according to their level in the hierarchy (fig. 3-c). Concepts that have multiple parents appear under each parent, i.e., potentially multiple times in the hierarchy.

Granularity Levels

As discussed in Section 2, we aim to support views at different levels of granularityfrom an overall view to regions based on the is-a hierarchy, and down to single mappings. To do so we introduce alignment modes. In similarities mode (fig. 3-a), a filled cell represents an existing mapping between a pair of concepts. In mappings mode (fig. 3-b), a filled cell indicates that there is at least one existing mapping between a pair of concepts or their descendants. The cell weight represents either the similarity value (in the former case), or the number of mappings (in the latter case). Each mode is focused on performing one of two tasks: to compare similarity values for a pair of concepts, and to identify regions in the alignments with few or many mappings. The latter task provides a starting point for exploration and highlights regions of interest where many or few mappings have been calculated. When a concept is expanded in mappings mode, a cell is shown for both the concept itself and its sub-concepts. This forms regions in the cube (as in fig. 3-c) where smaller cells indicate mappings deeper in the hierarchy.

Interactive Visual Exploration

Directly inherited from the Cubix prototype developed for Matrix Cubes, the Alignment Cube user interface provides a variety of interactions for visual exploration, shown in fig. 2: changing alignment modes (see above), cell color and size encodings, switching between individual views, adapting cell transparency, brushing and linking, as well as alignment slice reordering. The cubelet widget allows for a quick navigation between a set of predefined views. For example, cells can be filtered out by specifying minimum or maximum value thresholds using a range slider. This also allows to simulate different thresholds and explore what-if questions and cases. Entire alignments can be hidden. To support pattern discovery, the order of alignments (slices) in the cube can be changed to facilitate comparison. A specific order can be calculated based on measures of precision, recall and F-measure between the ontologies, or based on alphanumeric label sorting (labels representing matcher, tool or alignment name). Matchers from one family are then ordered together next to each other after sorting by label.

Compare and Contrast

As with Matrix Cubes, Alignment Cubes provides several views onto the data, resulting from manipulations of the 3D cube. The individual views are: (a) 3D view, (b) 2D projection on 2 of the orthogonal cube faces, (c) side-by-side layout of the cube's slices (along 2 of the orthogonal dimensions). The 3D cube provides an overview of the number of alignments, number, size, and distribution of cells (mappings). It helps identify regions of interest and thus drive the initial exploration phase, and can possibly yield some high-level insights (fig. 3). It allows for interactive rotation and zoom but suffers from the typical drawbacks of 3D visualization, including occlusion and perspective distortion. Projection views allow for a clutter-free aggregated view on all alignments by orthogonally overlapping cells (fig. 7). Side-by-side views provide the most detailed view onto the data by entirely decomposing the view and showing each alignment in detail (fig. 6). Individual views, together with the ability to vary cell size, color, and translucency, allow for flexible multi-perspective exploration of the entire data set. Each of the two projections (alignment topology and concepts network) is paired with its respective small-multiples view. Both projections/small-multiple pairs allow for investigating the behavior of matchers-the alignment topology pair focuses on the similarities and differences between the alignments as a whole, while the concepts network pair allows for analyzing the behavior of matchers for a particular concept.

Use Cases Support

This section revisits the tasks and use cases identified in Section 2 and demonstrates how our tool supports interactive visual exploration and comparative evaluation of multiple alignments in Subsection 5.1. We further show that Alignment Cubes satisfy requirements for ontology alignment evaluation systems in Subsection 5.2.

Comparing Alignments & Systems and Support for Comparative Evaluation

We demonstrate how the tasks discussed in Subsection 2.1 can be performed with our tool by conducting a walk through scenario. In this scenario we aim to answer analytical questions including the following: Are the same regions covered in all alignments? Do matchers agree or disagree? Are there consistently stable and changing regions? Do similarity values differ? Are there missing and wrong mappings? Could we obtain other insights? We focus on observations which would be problematic to obtain without a visual representation of the alignments, as was the case in, e.g., [START_REF] Dragisic | Experiences from the anatomy track in the ontology alignment evaluation initiative[END_REF]. 6 and7) appear sparse since the respective alignments are the final alignments for the OAEI evaluation campaign, and thresholds have already been applied to remove mappings with a low similarity value. Note that in the process of matcher development, selection and fine tuning (see UC1 and UC2), the matrices would often be denser since more potential mappings would be considered. Alignment Cubes would scale to such higher-density matrices, as the cubes were designed for dense dynamic networks in the first place [START_REF] Bach | Visualizing dynamic networks with matrix cubes[END_REF]. Exploration: Our exploration starts with the initial 3D cube view in mappings mode (fig. 4-a). The colors and sizes of cells show that most of the mappings (large red cells) are concentrated around the two sets of concepts between Person ( 4 ) and Event ( 3 ). In contrast, few mappings have been found between Organization and confOf:Contributionekaw:Document. To see the subconcepts of Person and Event, we expand these two concepts in both ontologies (fig. 5-a). After expanding these concepts, as the visualization is in mappings mode, the cells that appear smaller and lighter (because of this particular color scheme) indicate under which subconcepts the single mappings are located. We now collapse these concepts and return to the view in fig. 4-a. We see that all matchers have computed similar numbers for the Event concept pair, as the size of cells is more or less constant along the mapping dimension (cube depth).

However, somewhat larger differences in cell size can be observed along the depth dimension (across alignments) for the Person concept pair, which indicates a lower level of agreement across matching algorithms in this case. Hovering the respective cells with the mouse reveals that numbers vary between 4 and 8. Apparently, only RA (the last, backmost slice) contains a mapping between confOf:Topic & ekaw:Research Topic, meaning that we found a missing mapping: the single cell not aligned with others (fig. 4-a 1 ). For further exploration, we investigate different alignment orderings (by interactively reordering alignment slices). Reorder-by-name (fig. 4-b) clearly separates the three versions of the LogMap-family systems and allows to compare the performance for each version during the years. LogMap performs consistently better in terms of number of mappings found between 2012 and 2015 than in 2011, as visually indicated by the larger and more saturated (red) cells. To see if the same is true for similarity values, we switch to the similarities mode: if both modes show a similar picture, the system likely has used the same combination of alignment algorithms. To focus only on the LogMap alignments, we filter out all other alignments in fig. 5-b, leaving the cube halfempty. The similarity values computed by LogMap vary between the years (fig. 5-b), but not for its lightweight version, LogMapLite (not shown due to the filtering).

Focusing on the regions with many mappings, we expand the respective concepts in both ontologies and switch to the small-multiples view that shows alignment topology (fig. 6-a). In both modes the patterns for each of the versions are clearly noticeable. The lightweight LogMapLite in all four years (matrices 2 -5 ) consistently finds less mappings than the versions of LogMap between 2012 and 2015 (matrices 8 -11 ). LogMap 2011's pattern (matrix 12 ) is closer to the LogMapLite alignments than to the rest of the LogMaps. We may conclude that LogMapLite reuses LogMap 2011 algorithms and settings, and that there were likely significant changes in algorithms or their settings between LogMap 2011 and the following LogMaps. Further evidence about this can be found in the small-multiples view that shows concept-networks (fig. 6-b). Looking at the Event matrix ( 2 Going back to the initial 3D cube view in mappings mode (fig. 4-a), we make another observation: the cell in the top-left corner seems larger than the other cells aligned with it (fig. 4-a 2 ). We switch to the alignment topology view, change the cell color encoding to a uniform color (gray) and decrease transparency using the cell-opacity slider. In this aggregated view (fig. 7-a), cells that appear nested within each other (cells still have different sizes) indicate that the different matchers have computed different values for the same pair of concepts (fig. 7-a). This is the case with the top-left corner cell we noticed earlier. There are at least two nested cells between confOf:Contribution & ekaw:Document (fig. 7-a 1 ).

We expand both the confOf:Contribution and ekaw:Document concepts, as well as ekaw:Paper, which is a subconcept of ekaw:Document. We then switch to the concept networks projection view in similarities mode (fig. 7-b). We can now explore the matchers' behavior (matchers have become columns in this view) while hovering over the concepts from the ekaw ontology on the right of the matrix. Observing the mappings in RA (the left-most column) around confOf:Contribution, we can see that the mappings for confOf:Contribution ( 1 ) and confOf:Poster ( 2 ) are only found in RA, and that there is no mapping under confOf:Paper ( 3 ) in RA (while it is found by all other matchers).

To better observe where these mappings are, we switch to the concept-networks smallmultiples view (not shown

Ontology Alignment Evolution

We now describe how Alignment Cubes satisfies requirements for ontology alignment evolution systems (closely connected to UC3). A five-steps process for ontology evolution was proposed in [START_REF] Zablith | Ontology evolution: a process-centric survey[END_REF]. It can be generalized to ontology alignment evolution. The first step of the process focuses on the exploration of the ontologies. This is where an interactive visualization tool is most needed. Requirements to support the first step have been identified in [START_REF] Lambrix | Visualization for ontology evolution[END_REF]. In Table 1, we show an adaptation of these requirements for step 1, targeted at the alignment evolution. The category indicates whether we deal with inspection (I) or explanation (E).

An Alignment Cube addresses requirements F1-F9, F12-F13. It visualizes every alignment (F2) as a separate, labeled (F1) matrix showing both ontologies on its sides (F8). The cube, projections and small multiple views support visual identification and comparison of alignment revisions (F9), trends (F12), volatile and stable regions (F13) and changes between alignments (F3). The latter allows for deriving a history of changes made to mappings (F6). The alignment topology projection can be particularly useful for showing a summary of changes (F4). Additional matrices can be introduced to show specialized views of changes (F5) and provenance information (F7).

Discussion and Future Work

Validation of the approach: We demonstrated some of the analytic tasks that Alignment Cubes supports by describing a scenario in Section 5.1. Making such observations took only a couple of minutes with Alignment Cubes. We could identify the common trends between 12 alignments, and found five mappings missing from all 11 alignments and one wrong mapping in all 11 alignments. Furthermore, we found one incorrect mapping in five alignments (LogMap2011 and LogMapLite2012-2015). While we could likely have found missing and incorrect mappings via other means, this was achieved here easily, and in a very short time. The conclusions we draw come from integrating several observations, including all alignments after an exploration guided by the observed regions. Some observations could be made in more than one view, which allowed interpreting them in different contexts, and yielded additional opportunities to observe them if we had missed them earlier.

In Section 5.2, we showed that Alignment Cubes addresses many of the requirements expressed about understanding the evolution of ontology alignments. Alignment Cubes also supports requirements in the inspection and partial explanation dimensions from [START_REF] Ivanova | Requirements for and evaluation of user support for large-scale ontology alignment[END_REF]: representing dense region, ontologies, mappings and mappings suggestions, filtering, and providing a starting point for exploration. It also covers visual analytics and grouping aspects from [START_REF] Dragisic | User validation in ontology alignment[END_REF]. It could further support the analytic tasks identified in [START_REF] Aurisano | Visual analytics for ontology matching using multilinked views[END_REF]-evaluation of matcher performance, exploration and comparison and diagnosis (which comprises iterations of the other tasks). User Evaluation: Matrix Cubes has been evaluated with domain experts in Astronomy and Neurosciences, and have been found to be understandable after some initial learning [START_REF] Bach | Visualizing dynamic networks with matrix cubes[END_REF]. We have performed pilot tests with ontology alignment experts using the smallest task in the LargeBio track in the OAEI 7 and are currently planning more extensible usability tests with experts in ontology alignment in order to identify further use cases and to inform the design and development of future features. Scalability: The ontologies in this paper contained less than 100 concepts, and individual alignments had no more than 20 mappings. The tool was successfully tested using the ontologies (3696 and 6488 concepts in each) and all 12 alignments from the smallest task in the LargeBio track in the OAEI. Alignment Cubes have provided a compact overview for all of our examples, and should remain relatively compact with a higher number of mappings. Interactively collapsing and expanding concepts has proven useful to cope with the size of the ontologies and the mappings. Due to the size and depth of the ontologies, the small-multiples views required some pan and zoom on a regular workstation monitor. This can be addressed by filtering, or to some extent by using a large very-high-resolution display. Using larger display surfaces to show multiple views simultaneously is one of the directions identified in [START_REF] Ivanova | Applications of large displays: Advancing user support in large scale ontology alignment[END_REF]. Generalizability and Availability: Though we developed Alignment Cubes for ontology alignment, our adaptations to the original Matrix Cubes are generalizable to any (un)directed bi-graph. Examples include networks connecting authors to their publications, or documents to keywords, or proteins to certain biological functions. Future Features: Drawing from our experience with the tool so far, we have identified several directions for future extensions. Immediate improvements to consider include: adding support for different types of mappings (subsumptions, asserted, derived, etc.); exploring clustering and reordering algorithms to further support trend and pattern discovery; further supporting comparisons by visualizing the results of set operations (union, intersection, complement) as matrices. As discussed in [START_REF] Ivanova | Requirements for and evaluation of user support for large-scale ontology alignment[END_REF][START_REF] Dragisic | User validation in ontology alignment[END_REF], providing explanations about why and how a mapping has been computed supports decision making. We thus plan to explore different ways to compactly present such information to users.

In the longer term, we are interested in investigating the integration of Alignment Cubes with the SEALS platform used in OAEI. This will also open the stage for investigating advantages, drawbacks and methodological issues around the two evaluation approaches: comparative visual exploration at a detailed level, and overall assessment of the quality of alignments.

Conclusions

This work aims to take the evaluation of ontology alignments' quality beyond general measures such as precision, recall and F-measure. It identifies several use cases and shared tasks where comparison and exploration of multiple alignments at a high level of detail is needed. As the number of approaches and algorithms grows, capturing and analyzing their similarities and differences at varying levels of granularity will facilitate the understanding of their features, and provide additional means for alignment evaluation, hopefully contributing to driving the field forward. We see the evaluation of ontology alignments as an exploratory task, and discuss several activities that could be efficiently supported by an interactive tool-interactive visual exploration at different levels of granularity to perform compare & contrast tasks. Drawing from the field of data visualization, we adapt and extend a technique for dynamic network visualization. Our approach, Alignment Cubes, enables the interactive visual exploration of alignments and supports views at different levels of detail. We show their usefulness for the purpose of exploration of multiple alignments by describing a scenario where, in only a few minutes, we could identify several missing and incorrect mappings. This initial experience with the tool is encouraging, and we strongly believe that alignment evaluation should consider other means beyond precision, recall and F-measure, including visual exploration. We hope to integrate this tool with the SEALS platform used in the OAEI campaigns and evaluate its usefulness with developers and researchers involved and participating in them.

Fig. 1 :

 1 Fig. 1: From dynamic networks to Matrix Cubes and Alignment Cubes. (a) Adjacency matrices stacked to form a (b) 3-dimensional space-time cube (Matrix Cube). (c) Translation of the concept of Matrix Cubes to ontology alignment.

Fig. 3 :

 3 Fig. 3: Alignment Cubes for visualizing ontology alignments. Rows and columns of the cube represent ontology concepts, individual cells inside the cube represent mapping relationships. Each alignment, corresponding to a slice in the third dimension, is assigned a different color. (a) Default view in similarity values mode. (b) Initial view in mappings mode. (c) Mappings mode with cell weight color encoding after expanding the Events concepts in both ontologies.

Fig. 4 :

 4 Fig. 4: 3D view in mappings mode: (a) initial view and (b) after reordering by name.

Fig. 5 :

 5 Fig. 5: Views of Alignment Cubes: (a) after expanding concepts and (b) after filtering out several alignments.

  Fig. 6: Small-multiples views: (a) alignment topology (b) concept networks. Gray numbers have been added manually to the figure.

  ) and can see that the missing mappings are confOf:Poster & ekaw:Poster Paper and confOf:Contribution & ekaw:Paper. The wrong mapping is confOf:Paper & ekaw:Paper.

Fig. 7 :

 7 Fig. 7: Aggregated projections: (a) alignment topology and (b) concept networks.

  about/context of concepts in mappings I, E F9 compare different alignment versions I F10 search and query alignment I F11 query old versions using terminology of new version I, E F12 discover trends I, E F13 discover volatile and stable regions

Table 1 :

 1 Functionality for alignment evolution systems.

http://oaei.ontologymatching.org

http://seals-project.eu -Semantic Evaluation At Large Scale

http://www.ida.liu.se/ ˜patla00/publications/ISWC17 provides supplemental material to this submission: a screencast of the tool, and a downloadable version of the tool itself.

http://www.cs.ox.ac.uk/isg/projects/SEALS/oaei/2016/

Acknowledgements. This work has been supported by the Swedish e-Science Research Centre (SeRC), the Swedish national graduate school in computer science (CUGS) and the EU project VALCRI (FP7-IP-608142).


Rafael Morales Gonzalez

Caroline Appert

Gilles Bailly

Emmanuel Pietriga

TouchTokens: Guiding Touch Patterns with Passive Tokens

Keywords: Tangible interaction; Multi-Touch input ACM Classification H, 5, 2 : User Interfaces -Graphical user interfaces

Figure 1. TOUCHTOKENS are passive tokens that guide users' fingers to specific spatial configurations, resulting in distinguishable touch patterns.

INTRODUCTION

The main characteristics of multi-touch gestures performed on the capacitive screens that typically equip tablets, smartphones, touchpads, as well as some tabletops, are the number of fingers involved and the individual trajectories of those http://dx.doi.org/10.1145/2858036.2858041 fingers. Examples include 2-or 3-finger slide, and 2-finger pinch. But to the exception of a few research projects that consider touch points as chords [START_REF] Freeman | ShadowGuides: Visualizations for In-situ Learning of Multi-touch and Whole-hand Gestures[END_REF][START_REF] Ghomi | Arpège: Learning Multitouch Chord Gestures Vocabularies[END_REF], interactive systems ignore the relative spatial configuration of contact points; what we call a touch pattern.

Our goal is to enable users to perform gestures based on a set of distinct touch patterns, thereby increasing the richness of input vocabularies for tactile surfaces. Our approach relies on physical guidance, as it would be unrealistic to expect touch patterns to be executed consistently across users, or even over time by the same user. As the literature suggests that users adopt grasp strategies that depend on the object to manipulate [START_REF] Paulson | Object Interaction Detection Using Hand Posture Cues in an Office Setting[END_REF][START_REF] Vatavu | Automatic Recognition of Object Size and Shape via User-dependent Measurements of the Grasping Hand[END_REF], we investigate the potential of tangible tokens held on the surface to act as physical guides constraining the relative position of users' fingers.

We present TOUCHTOKENS, a novel interaction technique based on a set of easy-to-make passive tokens and a fast and simple recognition algorithm that can discriminate the unique touch pattern associated with each token in the set. 1 The approach features several advantages. First, physical tokens can provide space-multiplexed input by associating different controllers with different functions [START_REF] Fitzmaurice | Bricks: Laying the Foundations for Graspable User Interfaces[END_REF]. Second, tokens can alleviate issues related to discovery, exploration and learning inherent to gesture-based interaction [START_REF] Zhai | Foundational Issues in Touch-Surface Stroke Gesture Design: An Integrative Review[END_REF]. Finally, tokens provide haptic feedback that promotes eyes-free interaction [START_REF] Jansen | Tangible Remote Controllers for Wall-size Displays[END_REF].

TOUCHTOKENS make it easy to implement applications that combine multi-touch and tangible input at low cost. Such a combination has the potential to foster collaboration, support distributed cognition, and enhance the user experience [START_REF] Angelini | Tangible Meets Gestural: Comparing and Blending Post-WIMP Interaction Paradigms[END_REF][START_REF] Jetter | Materializing the Query with Facet-streams: A Hybrid Surface for Collaborative Search on Tabletops[END_REF][START_REF] Valdes | Exploring the Design Space of Gestural Interaction with Active Tokens Through User-defined Gestures[END_REF]. As opposed to other tangible systems that require electronic instrumentation (e.g., [START_REF] Bianchi | MagnID: Tracking Multiple Magnetic Tokens[END_REF][START_REF] Liang | GaussBits: Magnetic Tangible Bits for Portable and Occlusion-free Near-surface Interactions[END_REF]) or specific conductive material (e.g., [START_REF] Chan | CapStones and ZebraWidgets: Sensing Stacks of Building Blocks, Dials and Sliders on Capacitive Touch Screens[END_REF][START_REF] Kratz | CapWidgets: Tangible Widgets Versus Multi-touch Controls on Mobile Devices[END_REF]), our system relies on an algorithm that relies on standard multi-touch APIs and on passive tokens thats can be made of any non-conductive material, including wood or transparent acrylic.

We performed a formative user study to collect touch patterns, in which participants had to grasp and manipulate a set of twelve tokens of varying shape and size on a tabletop surface. The analysis of this pattern collection showed that people grasp the same token consistently across trials, but that it is quite difficult to identify a set of tokens and to design a robust recognition algorithm that works for all users. The two main sources of confusion are that different users may adopt different grasp strategies for the same token, and that one user may adopt the same strategy for distinct tokens. Based on these observations, we designed a second set of six tokens featuring notches that constrain users' grasp. These notches are designed to ensure a comfortable grasp while serving two purposes: 1) minimizing, for a given token, the variability of the contact points' relative position; and 2) maximizing the distinctiveness of touch patterns. We performed a summative study in which participants had to grasp and manipulate this set of tokens on both a tabletop and a tablet. Results show that our algorithm recognizes these touch patterns with an accuracy higher than 95%, and does so without any training or calibration. Application designers can map the gestures performed with these tokens to any command or parameter control, as illustrated in the examples introduced before the concluding discussion about limitations and future work.

RELATED WORK

TOUCHTOKENS makes use of physical tokens to augment the power of expression of multi-touch input, building upon tangible interaction and touch input research. Our review of related work is structured accordingly, giving an overview of projects that considered tangible tokens above interactive surfaces, or leveraged the power of expression of touch input.

Tangible tokens for tactile surfaces

Some tactile surfaces rely on diffuse illumination, which makes it possible to recognize both objects and hands in contact with the surface, using computer-vision algorithms to analyze the frames captured by IR cameras. Such techniques have been used, e.g., to track mice and keyboards [START_REF] Hartmann | Augmenting Interactive Tables with Mice & Keyboards[END_REF] or to design physical widgets [START_REF] Weiss | SLAP Widgets: Bridging the Gap Between Virtual and Physical Controls on Tabletops[END_REF]. The Conté tool [START_REF] Vogel | Conté: Multimodal Input Inspired by an Artist's Crayon[END_REF] is an artistic crayon that consists of an acrylic block that emits and reflects IR light. When tethered, its location and orientation can be tracked on diffuse illumination surfaces. Several projects rely on fiducial markers to ease the image-based analysis, such as the ReacTable [START_REF] Jordà | The reacTable: Exploring the Synergy Between Live Music Performance and Tabletop Tangible Interfaces[END_REF][START_REF] Kaltenbrunner | reacTIVision: A Computer-vision Framework for Table-based Tangible Interaction[END_REF], which offers a tangible environment for music composition. Tokens can also be stacked on top of one another, using fiducial markers with transparent areas [START_REF] Bartindale | Stacks on the Surface: Resolving Physical Order Using Fiducial Markers with Structured Transparency[END_REF] or optical fiber bundles [START_REF] Baudisch | Lumino: Tangible Blocks for Tabletop Computers Based on Glass Fiber Bundles[END_REF] to track them. Diffuse illumination hardware setups are somewhat bulky, however, and are thus mostly used for large surfaces such as tabletops.

Most touchscreens are capacitive: they detect a drop in capacitance when one or more fingers touch them. Various projects have investigated conductive objects. These objects contain a circuit of conductive material that links the areas that are in contact with the user's fingers to the areas that are in contact with the capacitive surface (the object's "feet"). As soon as the user touches an object, its feet become grounded and generate a drop in capacitance similar to a multi-touch pattern. Physical widgets [START_REF] Kratz | CapWidgets: Tangible Widgets Versus Multi-touch Controls on Mobile Devices[END_REF] rely on this technique, as do physical button pads that can be clipped to the edges of a device [START_REF] Yu | Clip-on Gadgets: Expanding Multi-touch Interaction Area with Unpowered Tactile Controls[END_REF], or more advanced objects that feature moving parts [START_REF] Chan | CapStones and ZebraWidgets: Sensing Stacks of Building Blocks, Dials and Sliders on Capacitive Touch Screens[END_REF][START_REF] Jansen | Tangible Remote Controllers for Wall-size Displays[END_REF] or that can be stacked [START_REF] Chan | CapStones and ZebraWidgets: Sensing Stacks of Building Blocks, Dials and Sliders on Capacitive Touch Screens[END_REF]. Designing conductive tokens is challenging: the feet must be positioned carefully and the circuit must be stable so that the generated touch pattern can be recognized consistently. As capacitive screens have been designed for human fingers, properties such as the feet's minimal size and the minimal distance between two feet, which depend on the device, must be carefully chosen [START_REF] Yu | Clip-on Gadgets: Expanding Multi-touch Interaction Area with Unpowered Tactile Controls[END_REF].

Other projects have explored more cost-effective ways of building conductive objects. Wiethoff et al. [START_REF] Wiethoff | Sketch-a-TUI: Low Cost Prototyping of Tangible Interactions Using Cardboard and Conductive Ink[END_REF] use cardboard and conductive ink. This works well for low fidelity prototyping, but does not scale with real usages. Blagojevic et al. [START_REF] Blagojevic | CapTUI: Geometric Drawing with Tangibles on a Capacitive Multi-touch Display[END_REF] report on a design experience where they have built a small set of geometric tools (ruler, protractor and set square) for a tabletop drawing application. They tested different construction strategies by combining different low-cost conductive materials (e.g., conductive ink, conductive foam, aluminium tape, copper wires). Their experience shows that making a physical tool conductive is quite difficult, as many factors have to be considered (consistent circuit, stability, friction with the screen, good grasp, etc.). In the end, the best design consisted of drilling holes in the tool and using conductive foam to cover the tool and fill the holes. In the panorama of capacitive tokens, PUCs [START_REF] Voelker | PUCs: Detecting Transparent, Passive Untouched Capacitive Widgets on Unmodified Multi-touch Displays[END_REF] are an exception: they rely on the principle of mutual capacitance so as to be detected even when users do not touch them. However, most systems have to be augmented with an additional calibration clip to cheat the implemented adaptive filtering that tends to interfere with the PUCs' detection. Some tangible systems work with magnetic tokens that modify the magnetic field incoming to the magnetometer built in mobile devices [START_REF] Bianchi | Designing Tangible Magnetic Appcessories[END_REF]. However, as a magnetometer reflects the sum of the magnetic fields it senses, supporting multiple tokens requires putting more than a simple magnet inside the tokens. Bianchi and Oakley [START_REF] Bianchi | MagnID: Tracking Multiple Magnetic Tokens[END_REF] propose to use a more elaborate electronic system that features a motor to make the mounted magnet spin at a specific frequency. Putting a grid of Hall sensors behind the surface, Liang et al. [START_REF] Liang | GaussBits: Magnetic Tangible Bits for Portable and Occlusion-free Near-surface Interactions[END_REF] get a 2D image of the magnetic field that can be analyzed to track the location and orientation of objects above the surface. Each object can also be shielded with a case made of galvanized steel to avoid attraction and repellence effects between several tokens [START_REF] Liang | GaussStones: Shielded Magnetic Tangibles for Multi-token Interactions on Portable Displays[END_REF].

Multi-touch input and power of expression

Researchers have considered several avenues to increase the power of expression of touch input, including finger identification, finger pressure, or finger impact in order to multiplex input by assigning one command per finger, pressure level, or impacting zone. Finger identification relies on pattern recognition techniques coupled with advanced sensors such as fingerprint scanners [START_REF] Sugiura | A User Interface Using Fingerprint Recognition: Holding Commands and Data Objects on Fingers[END_REF] or fiber optic plates [START_REF] Holz | Fiberio: A Touchscreen That Senses Fingerprints[END_REF]. Projects such as SimPress [START_REF] Benko | Precise Selection Techniques for Multi-Touch Screens[END_REF] or FatThumb [START_REF] Boring | The fat thumb: using the thumb's contact size for single-handed mobile interaction[END_REF] capture the size of the finger's contact area and assign two different meanings to a soft tap and a hard tap. It is even possible to capture both the normal and tangential components of the force applied on the surface using extra pressure sensors [START_REF] Heo | Force Gestures: Augmenting Touch Screen Gestures with Normal and Tangential Forces[END_REF]. Identification and amount of pressure of the finger in contact can also be assessed by classifying muscle activity in the forearm [START_REF] Hrvoje Benko | Enhancing Input on and Above the Interactive Surface with Muscle Sensing[END_REF]. Finally, TapSense [START_REF] Harrison | TapSense: Enhancing Finger Interaction on Touch Surfaces[END_REF] discriminates which part of the finger (nail, knuckle, pad or tip) hits the surface by using acoustic sensing. With the exceptions of SimPress and FatThumb, that capture two pressure levels based on the size of the contact area, all of the above techniques rely on tactile surfaces that are augmented with additional sensors. Some systems make use of whole-hand gestures (e.g., horizontal vs. vertical hand, straight vs. curved hand) for manipulating virtual objects [START_REF] Xiang Cao | ShapeTouch: Leveraging contact shape on interactive surfaces[END_REF][START_REF] Rekimoto | SmartSkin: An Infrastructure for Freehand Manipulation on Interactive Surfaces[END_REF][START_REF] Wigdor | Rock & Rails: Extending Multi-touch Interactions with Shape Gestures to Enable Precise Spatial Manipulations[END_REF][START_REF] Wu | Multi-finger and Whole Hand Gestural Interaction Techniques for Multi-user Tabletop Displays[END_REF], or invoking virtual tools by mimicking the hold of their physical counterparts [START_REF] Bartindale | SurfaceMouse: Supplementing Multi-touch Interaction with a Virtual Mouse[END_REF][START_REF] Harrison | TouchTools: Leveraging Familiarity and Skill with Physical Tools to Augment Touch Interaction[END_REF]. Most of these projects rely on tactile surfaces that give access to the shape of the whole contact region, and cannot run on regular capacitive surfaces, which have been developed for finger input and consequently deliver standard pointbased multi-touch coordinates only. One notable exception is the TouchTools system [START_REF] Harrison | TouchTools: Leveraging Familiarity and Skill with Physical Tools to Augment Touch Interaction[END_REF] that uses machine learning to recognize up to seven touch patterns associated with seven hand postures on a capacitive screen. A few systems can also recognize chord gestures. Finger-Count [START_REF] Bailly | Design and Evaluation of Finger-count Interaction: Combining Multitouch Gestures and Menus[END_REF] counts the number of contact points on the surface. Arpège [START_REF] Ghomi | Arpège: Learning Multitouch Chord Gestures Vocabularies[END_REF] supports more chords by relying on the contact points' relative position. The technique requires per-user calibration to record the fingers' natural position when the hand rests in a comfortable posture.

TOUCHTOKENS take a different approach and does not make the assumption that the fingers' relative position is always the same. The technique relies on different relative finger positions that users would adopt naturally when grasping a tangible token on a surface. Recognizing typical hand postures when people grasp objects has been investigated in experimental psychology to identify everyday objects and then infer users' activities (such as holding a mug or typing at the keyboard) [START_REF] Paulson | Object Interaction Detection Using Hand Posture Cues in an Office Setting[END_REF]. Experimental studies show that it is possible to distinguish objects that differ in their size [START_REF] Buchholz | Anthropometric data for describing the kinematics of the human hand[END_REF], shape (e.g., cylinder, pyramid, etc.) [START_REF] Santello | Gradual molding of the hand to object contours[END_REF] or both [START_REF] Paulson | Object Interaction Detection Using Hand Posture Cues in an Office Setting[END_REF][START_REF] Vatavu | Automatic Recognition of Object Size and Shape via User-dependent Measurements of the Grasping Hand[END_REF]. However, these studies assume that the system provides access to the whole hand posture, using advanced motion capture systems that can provide the position and orientation of all hand joints.

TOUCHTOKEN

The primary objective of TOUCHTOKENS is to guide the registration pose [START_REF] Freeman | ShadowGuides: Visualizations for In-situ Learning of Multi-touch and Whole-hand Gestures[END_REF] of multi-touch gestures on an interactive surface. TOUCHTOKENS take advantage of users' ability to grab physical objects in the real word. Our idea is that the geometry (shape and size) of an object impacts how users grab it. Different objects will thus have different touch patterns on the tactile surface, which can be discriminated. Touch patterns are recognized at registration and remain active until all contact points have left the surface. In particular, users can relax their grasp in the execution phase of their gesture [START_REF] Wu | Gesture Registration, Relaxation, and Reuse for Multi-Point Direct-Touch Surfaces[END_REF], thus reducing finger occlusion and enabling a larger range of motion. In this section, we describe how to build a system based on TOUCHTOKENS. Applications and limitations of the approach are discussed at the end of the paper.

Fabrication

TOUCHTOKENS require neither embedding electronics in the tokens nor augmenting the tactile surface with additional hardware (such as, e.g., a computer vision system), which makes setup easy. Tokens can be built from any nonconductive material such as wood, plastic, metal or glass, since the system only relies on the fingers' relative position, which is already provided by the tactile surface. This flexibility allows designers to easily prototype and test different TOUCHTOKENS variants with a 3D printer or a laser cutter. In particular, designers have a lot of control on the tokens' appearance. For tokens that have permanent roles associated with them, interface designers can engrave an icon or a label on them, or use a specific color. For temporary associations, end-users could adopt more volatile solutions, such as adding stickers or writing with an erasable pen if the chosen material affords it (e.g., pencil on a wooden token). Tokens can also be made of transparent material such as glass or acrylic, to avoid occluding the content displayed on the tactile surface.

Recognition

When grabbing a token with more than two fingers in contact with the surface, TOUCHTOKENS can infer its identity, and thus the corresponding registration pose, from the relative spatial configuration of the touch points. The recognition engine is initialized with one or more typical touch patterns per token and, when a touch pattern of at least three points occurs, the algorithm computes the distance between this input pattern and the set of template patterns. The recognized token is the one associated with the template that minimizes this distance metric.

Computing the distance between two touch patterns (input I:{I 1 , ..., I n } and template T :{T 1 , ..., T n }) is not straightforward, however. First, most tactile surfaces do not provide finger identification. Second, tokens have an arbitrary orientation on the surface. Figure 2 illustrates how our algorithm processes touch patterns in order to identify the best alignment between the reference template and actual input patterns, from which the distance is computed.

The key steps for identifying the best alignment are as follows: (1) compute the centroid C I of the three (or more) touch points; (2) generate all sequences of touchpoint labels (permutations) so that their IDs always appear in counterclockwise order; (3) rotate all these touch patterns so as to align vector ---→ C I I 1 with the x-axis. (4) The algorithm then translates touch patterns to align the input (C I ) and template (C T ) centroids. ( 5) It finally pairs the points in the permutation with the template's points in order to compute the distance, simply by summing all distances between paired points. The distance between reference template and actual input is given by the best input alignment, which is the permutation that minimizes this distance metric.

A typical implementation of the recognition engine amounts to about a hundred lines of code, and will work on any capacitive surface. The engine relies on simple geometrical features, which makes it easier to understand recognition errors compared to less transparent techniques such as those based on machine learning, that work as black boxes. The algorithm is very fast: recognition time scales linearly with the number of candidate templates. A Java implementation will be made available publicly, featuring both TUIO and Android APIs2 .

REGULAR TOKENS

TOUCHTOKENS rely on the hypothesis that the geometry of tokens impacts how users grasp them, resulting in distinguishable touch patterns. In order to test this hypothesis and identify a set of tokens that can actually be discriminated, we first ran a formative study in which participants had to grasp a set of twelve tokens that vary in shape and size.

Experiment design Token Set

We selected a set of 4 × 3 = 12 tokens (Figure 3) that vary in their shape (square, circle, rectangle, and triangle) and size (3cm, 4cm and 5cm). The choice of size was informed by informal tests, taking into account both human and technological constraints. The tokens should remain comfortable to grasp with at least three fingers, which entails bio-mechanical constraints on the minimum and maximum token size. Capacitive surfaces also impose a minimal distance between finger tips, which will be seen as a single point if too close to one another. Our tokens are made of wood and are 6mm thick. We had initially considered tokens 3mm thick, but those were too difficult to grab. The tokens' corners are also slightly rounded so as to avoid sharp wedges that could have hurt participants.

Types of interaction

Participants are seated in front of the tabletop (at the center of the long edge) and perform a series of trials with the different tokens (Figure 4). As illustrated in Figure 5, the graphical display always features a progress bar in the top-left corner and a picture of the token to use in the current trial in the topright corner. The action to be done with the token depends on the type of interaction (INTERACTION). The Global condition operationalizes the case where users invoke a global command with the token (e.g., launching an app); the Local 2. In the second phase (INTERACTION = Local), participants have to select the right token, put it on the cross (Figure 6), holding it still with at least three fingers for at least 1 second. The cross can be in five different LOCATION. These locations are chosen on a semi-circle roughly centered on the participant as in [START_REF] Olafsdottir | Prospective Motor Control on Tabletops: Planning Grasp for Multitouch Interaction[END_REF] (see Figure 6), as the token's location on the surface (relative to the participant) may influence the neutral hand posture and thus how the token is grasped. The distance between the touch pattern's centroid and the center of the cross must be at most 50px. If this distance is greater, the progress bar turns red and participants must perform the trial again.

3. In the third phase (INTERACTION = Path), participants must hold the token still with at least three fingers for a short period of 100ms. The background turns from gray to white. Participants then have to slide the token along the path indicated by purple arrows. In this condition, participants can plan a manipulation with the token, which may influence their initial grasp [START_REF] Olafsdottir | Prospective Motor Control on Tabletops: Planning Grasp for Multitouch Interaction[END_REF]. When sliding the token, they can lift some fingers but must keep at least one finger in contact with the surface. If they lift all fingers before having performed the whole gesture, the background turns back to gray and they have to start again. Figure 7 shows the six types of paths that participants had to follow with each token. We chose these tasks based on the taxonomy of multi-touch gestures from (Int-CCW and Int-CW), participants have to rotate the token around its center, as they would do with a physical circular knob. As soon as the touch pattern has been rotated by at least 45 • around its centroid, the background turns green to indicate that the trial has been successfully completed. Finally, for linear gestures (Lin-Left and Lin-Right), participants simply have to slide the token to match the amplitude and direction indicated by the arrow.

Participants and Apparatus

Twelve volunteers (3 female), aged 23 to 33 year-old (average 26.5, median 25.5), participated in the experiment. The experiment software was running in full screen mode on a 3M C3266P6 capacitive screen (display dimensions: 698.4 x 392.85 mm, resolution: 1920 x 1080 pixels) placed horizontally on a desk (Figure 4). A digital video camera on a tripod recorded participants' hand and arm movements. The experimental software was developed in Java 2D (JDK 7) and ran on a Mac Pro 2.8 GHz Intel Quad Core with 16GB memory, running Mac OS X 10.7.5.

Procedure

Participants are seated at the center of the long side of the tabletop. They receive instructions detailing the goal of the experiment and the different experimental tasks they will have to perform. In particular, the operator initially informs participants that the goal is to design a system that is able to recognize tokens based on users' grasp. He encourages them to be consistent in their grasp across trials with tokens that have the same shape. In order to identify which grasp is comfortable, the operator gives participants four tokens, one per shape with size = 4cm (Square 4 , Circle 4 , Rectangle 4 and Triangle 4 ), and asks them to manipulate each token a bit on the surface in order to choose a comfortable grasp. The operator then notes this grasp in his logs and the experiment starts.

As mentioned above, the experiment consists of three phases that are always presented in the same order:

• Phase 1 (INTERACTION = Global): 12 TOKEN × 5 repetitions = 60 trials. In this phase, the presentation order for the trials is randomized in order to observe if people are actually able to grasp the same token consistently across different trials that are not consecutive. To minimize the visual search time associated with identifying the right token to take, the operator printed 5 copies of each individual token and initially sorted the 60 tokens on the table, on the right side of the screen (Figure 4). After completion of these three phases, participants receive a questionnaire where they have to give a comfort score for each of the twelve tokens. The questionnaire features 12 Likert-scale type questions where participants have to give a rating between 0 (not comfortable to grasp at all) to 5 (very comfortable). The overall procedure lasted about an hour.

Results

We first tested if participants' grasps of the different tokens can be distinguished using the recognition strategy described in the previous section. To that end, we train our recognition algorithm using the first three trials of Phase 1 as templates for each token. This training strategy corresponds to what a system relying on a light training phase would require. 3 We then evaluate our algorithm on the remaining trials, i.e., (2 × 12 + 2 × 12 × 5 + 2 × 12 × 6) × 12 participant = 3456 trials.

A χ 2 analysis reveals that both INTERACTION (χ 2 (2, N = 3456) = 12, p = 0.002, φ = 0.06) and TOKEN (χ 2 (11, N = 3456) = 109, p < 0.001, φ = 0.18) have a significant effect on RECOG-NITION RATE. Figure 8 illustrates the observed differences between conditions. A finer analysis of TOKEN's effect on RECOGNITION RATE per INTERACTION shows that TOKEN 3 We tested our algorithm with different training strategies to accommodate more variability (e.g., considering templates picked from the three experiment phases) but there was no clear gain compared against the training cost it would entail for end-users. We then wanted to investigate the impact of the token subset's size on recognition rate. In order to identify the largest number of grasps that can be accurately discriminated for each participant, we computed all possible subsets of tokens among the initial set of 12. The total number of subsets comprising at least two tokens (TOKENCOUNT >= 2) is:

12

T okenCount=2 12 T okenCount = 2 12 -12 -1 = 4083
For each subset, we ran our recognition algorithm with the same training strategy (only the first three trials from experiment phase INTERACTION = Global) in order to compute, for this subset, the recognition rate per participant. We observe that the per-subset recognition rate across participants exhibits a very high variability. For example, if we consider subsets that have 7 tokens (TOKENCOUNT = 7), the "worst" subset has a recognition rate of 63% on average across participants (worst-performing participant: 31%, best-performing participant: 98%), while the "best" subset has a recognition rate of 81% on average across participants (worst-performing participant: 57%, best-performing participant: 100%).

Recognition rate per participant

In order to test how many distinguishable grasps can be recognized per participant, we report the maximal recognition rate for each value of TOKENCOUNT ∈ {2, ..., 12}. If a participant P gets a maximal recognition rate R for TOKENCOUNT=N, this means that there exists at least one set of N tokens that are recognized with R% accuracy on average for participant P. Figure 9 reports these recognition rates for the best-performing and worst-performing participants, as well as the average over all participants. The charts illustrate that our algorithm can accurately discriminate a high number of grasps for some participants (the best-performing participant has a recognition accuracy higher than 90% for up to 10 tokens in all INTERACTION conditions), while it performs quite poorly for others (the worst-performing participant has The second source of confusion comes from inter-grasp similarity: if a user chooses one grasp strategy for a given token that is very similar to the one he uses for another token in terms of similarity of the touch patterns, the two tokens will get confounded. Together, these two phenomena explain why we observe such a large variability across participants regarding the composition of the token sets that are recognized accurately.

Recognition rate between participants

Figure 9 reports the best set of tokens for each participant, and thus does not reflect the fact that the same subset of tokens can be very accurately recognized for one participant while it will be poorly recognized for another participant. We report the biggest sets of tokens that reach consensus among all our participants below (i.e., the sets of tokens that have a recognition accuracy of at least 90% for all participants):

• for INTERACTION=Global, we find 6 sets of 5 tokens ;

• for INTERACTION=Local, we find 13 sets of 3 tokens ;

• for INTERACTION=Path, we find 6 pairs of tokens ; • for all INTERACTION conditions undifferentiated, we find 8 sets of 3 tokens with an average of at least 90% accuracy for all participants.

Grasp strategies

Figure 11 summarizes the different grasp strategies that participants adopted for the different token shapes (extracted from an analysis of the operator's logs and video sequences recorded during the experiment). We observed that all participants use the same strategy for circles (C). Squares and rectangles receive less consensus, with three different strategies observed for each of them. The main strategy for squares uses three edges (S 1 ; 6/12). The two other strategies use only two edges, and differ in the distance between the two fingers on the same edge: small (S 2 ; 4/12) or large (S 3 ; 2/12). For rectangles, one strategy uses the two long edges only (R 1 ; 5/12). The two other strategies use three edges: two contact points on the short edges (R 2 ; 4/12) or on the long edges (R 3 ; 3/12). One of the grasp strategy for triangles makes use of a corner (T 2 ; 2/12), which was quite surprising. Two participants adopted it, but actually rated it as very uncomfortable.

To understand what kind of confusions occur in the recognition process, we implemented a visualization that displays all collected touch patterns using the best alignment computed by our recognition algorithm (Figure 10 was built with this tool). We computed the confusion matrix by considering the 27 types of touch patterns (3 size × 9 grasp strategies). The visualization tool was a good complement to the confusion matrix as (1) some confusions do not appear in the matrix if a template for one token is too close to a template for another token; and (2) the different grasp strategies were not adopted the same number of times, leading to numbers in the confusion matrix that could not be compared in an absolute manner. From this analysis, we draw a few take-away messages. The flat isosceles triangle of grasp strategy R 2 is very representative and well-recognized. T 2 is also representative, but is too uncomfortable to be further considered. In contrast, some postures are difficult to distinguish. For instance, touch patterns R 1 and R 3 often form an equilateral triangle similar to the one of T 1 . Finally, S 1 and C can also cause confusions.

TOKENS WITH NOTCHES

Our foundational hypothesis was that physical tokens constrain users' grasp in a consistent manner, which leads to consistent touch patterns that can be recognized with a high level of accuracy. The results of our formative experiment revealed that our hypothesis was only verified for some participants. We also observed significant variations in grasp strategies among users, which means that a set of tokens that works well for one user might not work so well for another user. As we aim at devising a solution that works effectively for all users in a consistent manner, we investigated a solution to decrease the different sources of variability.

We designed a new set of tokens, illustrated in Figure 13, similar to those considered in the formative study, but that feature notches. The purpose of these notches is to afford a particular grasp strategy, i.e., to suggest a specific way of positioning the fingers to grab a given token. The design of these tokens was guided by the following requirements. We wanted the token set to feature a wide range of shapes, as tokens should be easy to identify by visual and tactual perception [START_REF] Jack | Multi-touch Gestures for Discrete and Continuous Control[END_REF]. Sets that feature different shapes also provide better mnemonic cues, making it easier for users to remember token-command associations. Finally, the tokens should remain comfortable to grasp. Based on these requirements, we picked the most comfortable size for each shape (5cm), and added the circular and square tokens of 4cm, which were also rated as very comfortable (Figure 12). We limited our summative study to this set of six tokens which, together with all token manipulation gestures, already provides a rich input vocabulary.

The grasp strategies observed during our formative experiment (Figure 11) informed the positioning of notches on token shapes. The notches' dimensions were refined through trial and error: narrow and deep notches introduce corners under finger tips, which make them uncomfortable; large and shallow notches are more comfortable, but introduce tangential variability in finger position. Our final design tries to strike a balance, and consists of notches 15mm wide and 1.5mm deep. Tokens whose shape afforded variable grasp strategies in the previous experiment feature a dot that indicates where to put the thumb, as illustrated in Figure 13-a.

These new tokens are designed to strongly constrain how users grasp them. We hypothesize that this will result in significantly reduced level of variability, which should enable our approach to work without any training. For each token, we compute a representative touch pattern that will act as a universal template for all users. The touch pattern is derived from the notches' position, slightly offset from the token's edge along the normal to that edge, so as to better capture users' grasp (Figure 13-b). The exact value of this offset (5mm) is calculated from the average offset measured in trials performed with circular tokens in the previous experiment, comparing the radius of the circle that passes through the three touch points with the radius of the actual physical token. (The precise, vector-based description of these tokens, ready for laser-cutting or 3D printing, will be distributed publicly and is also part of the earlier-mentioned supplemental material available to reviewers.)

EXPERIMENT

We ran a controlled experiment to test users' ability to manipulate tokens with notches, and to evaluate our algorithm's accuracy when provided with the above-mentioned universal templates in combination with this particular kind of tokens. The experimental design is similar to that of the previous study, but uses the set of 6 tokens of Figure 13. We also include an additional DEVICE condition: participants perform the tasks on both the tabletop and a tablet. Because of the smaller size of the tablet, we exclude the Local condition when DEVICE=Tablet, as the different locations (Figure 6) are clearly too close to one another to impact users' grasp. Contrary to our formative experiment, participants did not receive any other instructions than to grasp the tokens using the notches. In particular, the operator never asked them to adopt a consistent grasp across trials for a given token.

Experimental design Procedure

Half of the participants started with the Tabletop, while the other half started with the Tablet. The strategy for counterbalancing the presentation order of trials is exactly the same as in the first experiment. The only difference lies in the Tablet condition, in which participants only performed Global and Path tasks (in this order), but not the Local task.

In The experimental setup for the Tabletop condition was exactly the same as in the previous experiment. In the Tablet condition, participants were seated at the same table, but had to hold the tablet during the whole experiment, as illustrated in Figure 14. The tablet (Samsung GT-P5110 Galaxy Tab 2) had a 256.7 x 175.3 mm display area with a resolution of 1280 x 800 pixels.

Results

As illustrated in Figure 15, the recognition rate in both DE-VICE conditions is very high: 98.7% on the Tabletop and 99.3% on the Tablet. A χ 2 analysis reveals that the effect of INTERACTION on RECOGNITION RATE is significant neither in the Tabletop condition (p = 0.8) nor in the Tablet condition (p = 0.3). However, TOKEN has a significant effect in both DEVICE conditions (Tabletop: χ 2 (5, N = 1944) = 30, p < 0.001, φ = 0.12 and Tablet: χ 2 (5, N = 1224) = 30, p < 0.001, φ = 0.16)). Actually, in the Tabletop condition, the RECOGNITION RATE is a bit lower for Circle 4 (95.6%) than it is for all other tokens (> 98.7%). The same is true for token Square 4 (96.5%) in comparison with all other tokens (> 99%) in the Tablet condition.

Interestingly, even if we realized a posteriori that the thumb marker (dot) is meant for right-handed users, our left-handed participant did not have any trouble manipulating the tokens. He simply put his thumb in the notch opposite to the dot, ignoring the latter. Of course, he was able to do so because our tokens feature an axis of symmetry. However, we expect that TOUCHTOKENS's approach can be used for arbitrary-shape tokens, including some that would not feature a symmetric touch pattern. In that case, users can still flip them to accommodate their handedness, provided that the tokens are flat. If a token cannot be flipped easily, a solution would consist in designing two variants: same shape but pattern of notches mirrored. When the pattern cannot be mirrored because of the shape's geometry, it is still possible to design two patterns, one for each handedness.

APPLICATIONS

The above results show that, using tokens with notches, it is possible to build robust applications that will take advantage of both gesture-based and tangible interaction. Application domains that would benefit from such type of input are quite varied and have already been discussed in the literature, including: geographical information systems [START_REF] Koike | Transparent 2-D Markers on an LCD Tabletop System[END_REF], database querying [START_REF] Jetter | Materializing the Query with Facet-streams: A Hybrid Surface for Collaborative Search on Tabletops[END_REF][START_REF] Ullmer | Tangible Query Interfaces: Physically Constrained Tokens for Manipulating Database Queries[END_REF], information management [START_REF] Rekimoto | DataTiles: A Modular Platform for Mixed Physical and Graphical Interactions[END_REF][START_REF] Ullmer | mediaBlocks: Physical Containers, Transports, and Controls for Online Media[END_REF] and music composition [START_REF] Jordà | The reacTable: Exploring the Synergy Between Live Music Performance and Tabletop Tangible Interfaces[END_REF]. We developed a set of proof-of-concept applications 4 to illustrate the different roles that TOUCHTO-KENS can play in an interactive system (see Figure 16). TOUCHTOKENS can act as controllers or filters, and can be used to manipulate both the content of an application or the presentation of this content. For instance, they can be used to adjust the parameters of a visualization, enabling users to focus more on the result of their actions as the manipulation of physical tokens decreases the demand on visual attention [START_REF] Ullmer | Tangible Query Interfaces: Physically Constrained Tokens for Manipulating Database Queries[END_REF]. We have developed a simple scatterplot visualization in D3 [START_REF] Bostock | D3 Data-Driven Documents[END_REF] to illustrate this idea. The different categories in the data (e.g., countries grouped by continent) are associated with different symbols (which have distinct shapes and colors), as is typically the case when visualizing multivariate datasets. One TOUCHTOKEN, with matching shape and color, is associated with each category and can be used to adjust the visual representation of the corresponding data points in the scatterplot: changing their size by rotating the token, and their opacity by sliding it. TOUCHTOKENS can be transparent, in which case they will typically be used as physical see-through tools [START_REF] Bier | Toolglass and Magic Lenses: The See-through Interface[END_REF][START_REF] Büschel | T4 -Transparent and Translucent Tangibles on Tabletops[END_REF], altering the content that falls below the token (e.g., filtering) or changing its visual attributes (e.g., rendering). For instance, we have developed a simple mapping application in which tokens are associated with different layers. The tokens act as magic lenses [START_REF] Bier | Toolglass and Magic Lenses: The See-through Interface[END_REF] that reveal the corresponding layer while leaving the context untouched. See-through tools can also be used to move content in the workspace, as demonstrated in our simple game, where transparent tokens control the location and orientation of individual characters.

TOUCHTOKENS can also act as a receptacle for, or tangible representative of, digital content. Tokens then give access to the associated content [START_REF] Holmquist | Token-Based Access to Digital Information[END_REF]. One of our demo application illustrates how TOUCHTOKENS can be used for access control. Tokens can be used, e.g., to launch applications whose icons are otherwise invisible or disabled on the tablet's homescreen, enabling the device to be shared with family (parental control) and friends with some restrictions. Access to private content can be made even more secure by requiring that the token be put in a specific location, or that a particular gesture be performed with it. Our last application demonstrates the use of TOUCHTOKENS as digital containers. Users can reify photo albums into tokens, and add a picture to an album by holding the corresponding token above it. They can then display an album's content as a grid of thumbnails by rotating the token on the surface, or launch a slideshow by sliding it.

DISCUSSION AND FUTURE WORK

Main findings

We ran a formative experiment to investigate the possibility of recognizing individual tokens by categorizing their associated touch patterns. We were hypothesizing that differences in token shape and size might be sufficient to accurately discriminate those patterns. Our results revealed significant inter-user variability in terms of accuracy: our algorithm can recognize up to ten touch patterns with more than 90% accuracy for some users, while for other users, its accuracy falls down as soon as three or more tokens are in the set. This variability comes from two sources: 1) some users employ different grasp strategies for the same token; 2) some users employ grasp strategies for different tokens that yield very similar touch patterns.

Based on these observations, we then designed a set of six tokens featuring notches aimed at reducing this variability while remaining comfortable to grasp. A summative experiment showed that with this set of tokens, our recognizer has a minimum accuracy over all participants higher than 95% (avg. 98%), and this without any training. Augmented with notches, TOUCHTOKENS offer a low-cost, yet reliable, solution for enabling tangible interaction on multi-touch surfaces.

As mentioned earlier, we make this recognizer freely available, along with vector-based templates for the tokens.

Alternative recognition strategies

Our algorithm is fast, robust, and easy to implement. It also features the best recognition rate among all alternatives that we implemented and tested on the data collected during our formative study. Alternative approaches we considered led to significantly poorer performance. In particular, we tested k-Nearest-Neighbour (k=1 and k=3) and SVM algorithms, using both raw data and describing features. The raw data was pre-processed to make it independent from rotation angle and finger identification. The describing features we considered included the touch envelope's area, as well as various descriptive statistics (min, max, mean, median and standard deviation) for measures such as point-centroid distance, distance between successive points, distance between any pair of points, etc. These machine learning approaches yielded recognition rates ranging from 50% to 85% per participant. Compared to this, the analytical approach detailed in this paper, which consists in aligning touch patterns using their centroid as a reference point, works much better. We also considered using as a reference point the center of the best-fit circle (i.e. the circle that passes through three touch points while minimizing the distance to all remaining points) rather than the centroid, but results were slightly worse. The recognition rate was lowered by about 3% on average.

Future work

After this first investigation, we plan to study more systematically the limits of our approach, to see how it can scale to larger sets of tokens and/or to tokens that have varying geometries. We want to better characterize the minimal difference between two touch patterns, in order to be able to automatically position notches that meet our requirements: create tokens that are comfortable to grasp and that our algorithm can recognize with a high level of accuracy.

We also plan to conduct a fine-grained analysis of the fingers' traces on the surface at the precise moment they are lifted off. We want to investigate if these traces provide enough data to find out whether the token is still on the surface or not. Indeed, when lifting her fingers off the surface, the user might leave the token on it, or she might remove it. This would allow us to support additional interactions, such as when placing multiple tokens on the tactile surface to express, e.g., layout and alignment constraints [START_REF] Frisch | Grids & Guides: Multi-touch Layout and Alignment Tools[END_REF] or advanced database queries with networks of tokens [START_REF] Jetter | Materializing the Query with Facet-streams: A Hybrid Surface for Collaborative Search on Tabletops[END_REF].

Figure 2 .

 2 Figure 2. Template and input touch pattern alignment process.

Figure 3 .

 3 Figure 3. Set of tokens used in the first study (size ∈ 3cm, 4cm, 5cm).

Figure 4 .Figure 5 .

 45 Figure 4. Experimental setup.

Figure 6 .

 6 Figure 6. In the INTERACTION = Local condition, participants have to put the token at a specific location (LOCATION ∈ 0 • , 45 • , 90 • , 135 • , 180 • ).

Figure 7 .

 7 Figure 7. In the INTERACTION = Path condition, the participant has to put the token on the surface and slide it along a specific path (PATH ∈ {Ext-CCW, Ext-CW, Int-CCW, Int-CW, Lin-Left, Lin-Right}).

•

  Phase 2 (INTERACTION = Local): 12 TOKEN × 5 LOCA-TION × 2 repetitions = 120 trials. The order of TOKEN × LOCATION is randomized across participants. The 2 repetitions per TOKEN × LOCATION condition are presented one after another to limit the length of the experiment. • Phase 3 (INTERACTION = Path): 12 TOKEN × 6 GESTURE× 2 repetitions = 144 trials. As in phase 2, the order of TO-KEN × GESTURE conditions is randomized across participants, with the 2 repetitions presented one after another.

Figure 8 .

 8 Figure 8. Recognition rate per INTERACTION (left) and per TOKEN (right). Error bars represent the 95% confidence interval.

Figure 9 . 9 4 4 Figure 10 .

 994410 Figure 9. Recognition rate per INTERACTION × TOKEN

Figure 10 displays

 10 Figure10displays the 27 touch patterns we have collected for Triangle 4 for two participants. It illustrates two extreme levels of intra-grasp variability. Participant 1 (left) grasps token Triangle 4 in a very consistent manner, while Participant 9 (right) demonstrates much more variation in how he grasps it, challenging our recognition strategy. The second source of confusion comes from inter-grasp similarity: if a user chooses one grasp strategy for a given token that is very similar to the one he uses for another token in terms of similarity of the touch patterns, the two tokens will get confounded. Together, these two phenomena explain why we observe such a large variability across participants regarding the composition of the token sets that are recognized accurately.

Figure 11 .

 11 Figure 11. The nine grasp strategies observed in Experiment 1

Figure 12 .

 12 Figure 12. Comfort score per token. Error bars represent the 95% confidence interval.

Figure 13 .

 13 Figure 13. (a) The 6 tokens with notches. (b) The touch point's location in the template is offset by 5mm along the normal to the token's edge.

Figure 14 .

 14 Figure 14. Experimental setup in the Tablet condition.

  the Tabletop condition, we collected 12 participants × 6 TOKEN × (5 [Global] + 2 × 5 LOCATION [Local] + 2 × 6 GESTURE [Path]) = 1944 trials. In the Tabletop condition, we collected 12 participants * 6 TOKEN × (5 [Global] + 2 × 6 GESTURE [Path]) = 1224 trials. Participants & Apparatus 12 volunteers (3 female), aged 23 to 39 years-old (average 26.4, median 24.5), one left-handed, participated in this experiment. Five of them had participated in the previous study.

Figure 15 .

 15 Figure 15. Recognition rate per TOKEN in the Tabletop (left) and Tablet (right) conditions. Error bars represent the 95% confidence interval.

Figure 16 .

 16 Figure 16. Proof-of-concept applications: access control, tangible magic lenses, character controllers in a game, data visualization.

Implementations of the algorithm and vector descriptions of the tokens ready for 3D-printing or laser-cutting are available at https://www.lri.fr/~appert/touchtokens/.

It is part of the earlier-mentioned supplemental material made available to reviewers.

All demonstrated in the companion video.