Benjamin Bach

Emmanuel Pietriga

Ilaria Liccardi
email: ilaria.liccardi@inria.frglegostaev@gmail.com

Gennady Legostaev

OntoTrix: A Hybrid Visualization for Populated Ontologies

Keywords: H.5.2 [Information Interfaces and Presentation]: User Interfaces Design, Human Factors Semantic Web, Exploratory Visualization, Graphs, Matrices

Most Semantic Web data visualization tools structure the representation according to the concept definitions and interrelations that constitute the ontology's vocabulary. Instances are often treated as somewhat peripheral information, when considered at all. These instances, that populate ontologies, represent an essential part of any knowledge base, and are often orders of magnitude more numerous than the concept definitions that give them machine-processable meaning. We present a visualization technique designed to enable users to visualize large instance sets and the relations that connect them. This hybrid visualization uses both node-link and adjacency matrix representations of graphs to visualize different parts of the data depending on their semantic and local structural properties, exploiting ontological knowledge to drive the graph layout. The representation is embedded in an environment that features advanced interaction techniques for easy navigation, including support for smooth continuous zooming and coordinated views.

INTRODUCTION

Significant research and development effort has been dedicated to the design of visual tools for the Semantic Web [START_REF] Katifori | Ontology visualization methods-a survey[END_REF]. By making use of the richer capabilities of graphical representations, as opposed to textual representations such as RDF/XML or N3, and by abstracting from the complex syntactic details of the latter and explicitly representing relations, visual tools aim at providing better cognitive support [START_REF] Ernst | Cognitive support for ontology modeling[END_REF] to users, from knowledge engineers to domain-expert end-users. They provide users with interactive representations of the data based upon state-of-the art information visualization techniques, better supporting tasks such as ontology understanding, discovery, search, comparison and mapping.

Most tools structure the visualization according to the concept definitions and interrelations that constitute the ontology's vocabulary (the TBox in Description Logics). While many of them do B. Bach, E. Pietriga, I. Liccardi and G. Legostaev. OntoTrix: A Hybrid Visualization for Populated Ontologies. In WWW '11: Proceedings of the 19th international conference on World Wide Web, To appear, ACM, March 2011. Authors Version support the visualization of instance (ABox) data, instances are often treated as somewhat peripheral information. The visualization is mainly structured according to the TBox, instances that constitute the ABox being treated as leaf nodes in this tree or graph structure. Exceptions to this general observation exist, but either give a limited view of the ABox or use conventional node-link diagram representations that do not scale beyond a few hundred nodes. Instances populate ontologies and represent an essential part of the overall knowledge base. Understanding instance-level data might be easier for users because of their lower level of abstraction compared to the definition of concepts based on OWL constructs, but instances will often be orders of magnitude more numerous than the definitions that give them machine-processable meaning (see, e.g., many of the datasets currently part of the Linking Open Data graph). As such, the visualization of instance-level data poses different but real challenges that remain to be addressed.

We present OntoTrix, a visualization technique designed to enable users to visualize, and navigate in, large instance sets and their relations. The technique is based on a hybrid network visualization that uses both node-link and adjacency matrix representations (Figures 1 and 3) to visualize different parts of the data depending on their semantic and structural properties.

ONTOTRIX

Ontology graphs contain many nodes and edges, and are often non planar. Two main issues with node-link diagram representations of such graphs are their inefficient use of screen real-estate and edge crossings that make dense regions difficult to read, both eventually causing scalability problems. A well-known alternative to node-link diagrams for graph visualization are adjacency matrices [START_REF] Henry | Nodetrix: a hybrid visualization of social networks[END_REF]. Nodes are represented as rows and columns, and edges as filled cells at the intersection of connected rows and columns. While node-link diagrams are good at showing the structure of relatively small and sparse graphs, adjacency matrices are very effective at showing large (better use of screen real-estate) and dense (no edge crossing) graphs. However, adjacency matrix representations are much less familiar to users than node-link diagrams, and make tasks that involve following paths in the graph more difficult [START_REF] Henry | Nodetrix: a hybrid visualization of social networks[END_REF], significantly increasing the user's cognitive load.

Our technique is inspired by a hybrid visualization called Node-Trix originally introduced by Henry et al. [START_REF] Henry | Nodetrix: a hybrid visualization of social networks[END_REF] and applied to social networks. The technique is very efficient at visualizing locally dense but globally sparse networks, representing the overall structure of the network using a node-link diagram and the dense subgraphs that represent communities using matrices. While the graph structure of ontologies might not always share the smallworld characteristics of social networks, we believe that such a hybrid representation, combined with appropriate interaction tech- niques, can be an efficient means to perform exploratory visualization of large ontology instance sets. NodeTrix was originally devised for very simple, undirected social network structures that only feature one type of node (actors) and one type of relation between actors. In ontologies, instances belong to different (and possibly multiple) classes, and are connected by different types of object properties. In OntoTrix, we encode the type of object property -a categorical variable -using color: different property types are mapped to different color hues. In the property hierarchy visualization window (Figure 3-D), property types are laid out hierarchically using a radial tree layout (see also Figure 2-a). Users can dynamically change the color hue of a property simply by dragging it, positions on the circle being mapped to color hues (HSB color model). Edges that connect instances that belong to the same matrix are represented by filling the corresponding cell in the matrix with the appropriate color. If several properties connect the same two nodes, the cell is sliced horizontally, each slice colored with one of the property types.

Local Magnification of node Judea with a Sigma Lens

If the graph is directed, matrices are usually read from row to column. We follow the same convention in OntoTrix, and further convey direction by only filling half of the cell to symbolize an arrow head (Figure 2-b). This also gives us some latitude to represent additional information such as symmetrical properties (filling the entire cell) and inverse relationships (filling the other half with the inverse property's color). Rows and columns in matrices are reordered using the Reverse Cuthill-McKee algorithm so that clusters within matrices can better be identified. For edges connecting in-stances that belong to different matrices (Figure 2-c), we visualize edge direction by varying from a shade of gray that is lowly contrasted with respect to the background color to the highly saturated color mapped to the object property type [START_REF] Holten | A user study on visualizing directed edges in graphs[END_REF]. Arrow heads are no longer required, thus minimizing occlusion and cluttering.

Matrices in NodeTrix basically correspond to highly-connected groups of actors, i.e., dense subgraphs that represent social communities. In OntoTrix, we propose different methods for grouping instances into matrices, yielding different perspectives on the data.

Density: This first method is similar to the one used in Node-Trix: instances are clustered in matrices depending on density, taking into account all object properties between instance nodes. Clustering by density is driven by the LinLog energy model [START_REF] Noack | Energy-based clustering of graphs with nonuniform degrees[END_REF] that will also be used to compute the initial layout.

Global class membership: This method groups instances into matrices according to class membership only. The user can specify what classes in the hierarchy will be used to compute groupings.

Local class membership: This method represents a tradeoff between the previous two. From an initial grouping based on density, all nodes are grouped together on a per-matrix basis according to class membership as described above (performing a reordering of columns and rows). As a next step, each of the original matrices can be optionally split into smaller matrices corresponding to the computed class membership groups. As a result of this process, several matrices corresponding to the same class may be created. Those can be merged back together in a single matrix. The representa- tion is then equivalent to the one that would have been obtained by directly grouping with the Global class membership method.

Property type: This last method clusters resource nodes into matrices according their object properties. Properties considered irrelevant can be filtered out: those are still visible, but dimmed so that selected properties stand out.

To compute the initial representation, matrices are treated as the nodes of a higher-level aggregate graph. The edges of this graph are computed according to the object properties connecting ontology instance nodes that belong to separate matrices. As mentioned earlier, LinLog is also used to compute the layout, as it can take into account the size of nodes in the layout process (matrices can have very different sizes). After having grouped instances into matrices according to one of the above-described methods, we construct the aggregated graph structure, whose nodes are the matrices and single nodes that do not belong to a matrix, if any. Node size depends on the number of elements in the associated matrix, and edge weight depends on the number of object properties in the actual ontology graph that link instances in both matrices. OntoTrix then lays out matrices and single nodes according to the positions computed by LinLog for this aggregate graph structure, and draws cubic curves for each object property connecting two instances that belong to different matrices. These are not the edges of the aggregate graph, which were only used for the layout computation, but the actual object properties relating instance nodes.

Beyond improvements in terms of readability, we believe that this hybrid visualization features an interesting property that is related to the above view of matrices as aggregates of instance nodes for the layout process. These aggregates will of course depend on the structure of the ontology and on the grouping method selected. But often, they will by themselves represent interesting entities, not explicitly represented in the ontology, but that bear semantics. For instance, when visualizing a social network such as a co-authorship network in NodeTrix, matrices are used to represent dense subgraphs. These subgraphs will often correspond to research laboratories, or to a group of people led by a prominent researcher representing one particular research direction or theme. Each matrix can be seen as a single, compound graphical element that graphically reifies these implicit entities, thus helping users identify them.

The higher level of granularity of these clusters implies an inherently multi-scale representation that can help users identify entities of interest and smoothly navigate between them according to the visual information seeking mantra (overview first, zoom and filter, then details-on-demand [START_REF] Shneiderman | The eyes have it: A task by data type taxonomy for information visualizations[END_REF]). Taking Figure 3 seems to be three main large communities in the social network visualized. While matrices [0] and [START_REF] Henry | Nodetrix: a hybrid visualization of social networks[END_REF] look fairly similar (cells in both matrices have similar colors indicating that they contain instances linked with the same properties), matrix [START_REF] Entremont | Using a degree of interest model to facilitate ontology navigation[END_REF] looks different even from an overview, which could lead the user to investigate one of the two sets more closely. Similarly, patterns between or within matrices can often be observed and guide navigation, such as the single column in matrix [0] in Figure 3 featuring many green cells (a particular property shared by most instances populating this particular matrix), or the central actor in Figure 1.

With proper labeling, OntoTrix can also provide some basic form of semantic zooming. When grouping by class membership in On-toTrix, matrices obviously represent groups of similar instances. We thus label each matrix with the associated class name (Figure 1). When grouping by other methods, matrices cannot easily be tagged as there is no explicit information about the grouping, that stems from the purely structural clustering of the graph. Matrices might still represent interesting entities, but will have to be labeled manually and are currently assigned a random identifier.

TASK AND COGNITIVE SUPPORT

The OntoTrix environment features four main views presented in Figure 3. The main view (A), contains the OntoTrix representation of the instance set. (B) provides an interactive bird's eye view of (A). The class hierarchy is visualized in (C) as a node-link diagram. The property hierarchy in (D) uses a radial tree layout. All views are implemented with the ZVTM user interface toolkit [START_REF] Pietriga | A toolkit for addressing hci issues in visual language environments[END_REF] and support smooth continuous zooming. Most visual transitions are smoothly animated to lower the user's cognitive load when relating the two states. This includes transitions when switching between different grouping methods, e.g., from density to local class membership. This particular transition is currently limited to fading in/out the new/old matrices while trying to preserve their spatial position. More elaborate transitions using elaborate morphing techniques [START_REF] Henry | Nodetrix: a hybrid visualization of social networks[END_REF] Numerous interactive features are built in the Ontotrix environment to help users visualize large sets of instances. As OntoTrix is currently limited to visualization and does not support in-place editing, most supporting features are related to navigation for understanding, discovery and search [START_REF] Ernst | Cognitive support for ontology modeling[END_REF]. We present these features using relevant items from the categorization of tasks by Katifori et al. based on earlier work by Shneiderman [START_REF] Katifori | Ontology visualization methods-a survey[END_REF] and echoed in the principles enunciated in [START_REF] Entremont | Using a degree of interest model to facilitate ontology navigation[END_REF].

Overview: Users are presented with an overview of the entire data in all views when a new ontology is loaded. As discussed earlier, matrices can be seen as coherent aggregations of instances which, together with proper labeling, provide a multi-scale and overview-compatible representation of the ontology [START_REF] Ernst | Cognitive support for ontology modeling[END_REF].

Zoom: All views being implemented with a ZUI toolkit [START_REF] Pietriga | A toolkit for addressing hci issues in visual language environments[END_REF], users can smoothly pan and zoom-in on items of interest. Global context is retained thanks to the bird's eye view (Figure 3-B). Objects have a specific location in space, thus ensuring better spatial knowledge preservation (as opposed to, e.g., expanding trees or node-link diagrams laid out using spring-based algorithms).

Filter: Properties can be selected and unselected in the object property hierarchy (Figure 3-D). Properties can thus be removed by type. When grouping matrices by property type, properties not selected are still visible but rendered with a lowly-contrasted color.

Details-on-demand: Data properties associated with nodes popup on demand when clicking inside a node, enabling comparisons between nodes, something difficult with non-persistent details-ondemand techniques such as tooltips, that require memorizing the previous value(s). At any given zoom level, a region of the view can be magnified (up to 14x) using a Sigma Lens [START_REF] Pietriga | Representation-independent in-place magnification with sigma lenses[END_REF] providing a focus+context view (right-hand side of Figure 1). Additional techniques inspired by work on topology aware navigation in large networks [START_REF] Moscovich | Topology-aware navigation in large networks[END_REF] are currently being implemented to further facilitate navigation. For instance, when zoomed-in on a large matrix, node labels might not be visible inside the viewport. Hitting a shortcut key temporarily brings row and column labels inside the viewport (Bring & Go). We are also implementing the Link sliding technique that will facilitate "jumping between [related] concepts[/instances]" [START_REF] Ernst | Cognitive support for ontology modeling[END_REF] located in different matrices.

Relate: All views are coordinated. For instance, hovering a node in the class hierarchy view highlights all corresponding instances in the OntoTrix view. Hovering a node in the property hierarchy view highlights all corresponding rows and columns in matrices, as well as corresponding edges between matrices. Classes declared as being in the domain or range of the property are highlighted in the class hierarchy, and conversely. Changes to the color hue of a property type in the property hierarchy view get dynamically propagated to the OntoTrix view. Hovering an instance in the OntoTrix view highlights all nodes from owl:Thing down to the actual class the instance is a member of, and highlights all properties in the property hierarchy that are used to relate that instance to other instances.

Search: Specific instances can be searched for; the main view smoothly pans and zooms to each matching instance sequentially.

IMPLEMENTATION

Rather than a full-featured ontology development environment, we consider OntoTrix as a new visualization technique that complements existing solutions, and could be integrated into applications such as Protégé [START_REF] Knublauch | The Protégé OWL Plugin: An Open Development Environment for Semantic Web Applications[END_REF]. OntoTrix is implemented in Java. The user interface is based on the ZVTM user interface toolkit [START_REF] Pietriga | A toolkit for addressing hci issues in visual language environments[END_REF]. LinLogLayout [START_REF] Noack | Energy-based clustering of graphs with nonuniform degrees[END_REF] is used for layout and clustering (grouping by density), Jena 2 for loading ontologies, and the TDB backend for storing them. The built-in OWL transitive reasoner is enabled by default, providing a complete classification of the ontology, i.e., calculating the complete class and property hierarchies. Additional reasoning can be performed before storing and visualization using one of the Jena reasoners or an external reasoner such as Pellet [START_REF] Parsia | Pellet: An OWL DL Reasoner[END_REF]. To evaluate the performance of OntoTrix, we performed tests with a set of ontologies ranging from a few hundred to several thousand instances and relations. Results are reported in Table 1, and show that loading times start to degrade when we try to visualize several tens of thousands of statements. While larger ontologies exist, they cannot be effectively visualized in their entirety with OntoTrix or any other tool we are aware of.

Figure 1 :

 1 Figure 1: Region of the NTN ontology corresponding to men and women who live in cities in Judea, and people related to them.

Figure 2 :

 2 Figure 2: Conveying edge direction: (a) Mapping property type to color hue for units.owl -Semantic Web for Earth and Environmental Terminology; (b) Matrix: milli_meter derives from meter, and has prefix milli ; (c) Node-link: lux is a product of candela and meterSquare, perCandela is derived from unit candela.

Figure 3 :

 3 Figure 3: OntoTrix Interface Overview: (A) Main NodeTrix view, (B) Bird's eye view, (C) Class hierarchy view, (D), Property hierarchy view. Visualizing 724 instances (49 classes) and 1 636 object properties (29 definitions) from the NTN ontology.

Table 1 :

 1 are being investigated.Tests performed with default OWL transitive reasoner, on a 2.26GHz Quad-Core Mac Pro (OS X 10.6.4). Java 1.6 set with a start and max memory heap sizes of 512MB resp. 2GB.1 http://sweet.jpl.nasa.gov/1.1/units.owl 3 http://www.semanticbible.com/ntn/ntn-view.html Performance

	Ontology	Class	Object Property	Data Property	Instances	Object	Total number of	Graphical	Parsing	Total
		definitions	definitions	definitions		properties	statements (TBox+ABox)	objects	time	time
	Units 1	13	3	5	103	146	438	1715	1.6s	2.7s
	Wine 2	138	16	1	206	246	4 547	3 296	5.5s	7.5s
	NTN 3	49	29	9	724	1 636	4 702	17 946	3.6s	10.9s
	SC 4	29	8	5	3 053	10 105	23 665	67 480	4.8s	73.5s

http://www.w3.org/TR/2003/CR-owl-guide-20030818/wine 4 http://www.mindswap.org/ontologies/SC.owl


Emmanuel Pietriga
email: emmanuel.pietriga@inria.fr

Olivier Bau
email: bau@lri.fr

Caroline Appert
email: appert@lri.fr

Representation-Independent In-Place Magnification with Sigma Lenses

Keywords: Graphical user interfaces, Visualization techniques and methodologies, Interaction techniques, Evaluation/methodology ✦

Focus+context interaction techniques based on the metaphor of lenses are used to navigate and interact with objects in large information spaces. They provide in-place magnification of a region of the display without requiring users to zoom into the representation and consequently lose context. In order to avoid occlusion of its immediate surroundings, the magnified region is often integrated in the context using smooth transitions based on spatial distortion. Such lenses have been developed for various types of representations using techniques often tightly coupled with the underlying graphics framework. We describe a representationindependent solution that can be implemented with minimal effort in different graphics frameworks, ranging from 3D graphics to rich multi-scale 2D graphics combining text, bitmaps and vector graphics. Our solution is not limited to spatial distortion and provides a unified model that makes it possible to define new focus+context interaction techniques based on lenses whose transition is defined by a combination of dynamic displacement and compositing functions. We present the results of a series of user evaluations that show that one such new lens, the speed-coupled blending lens, significantly outperforms all others.

INTRODUCTION

B IFOCAL display techniques complement conven- tional navigation techniques such as pan & zoom, typically used in 2D multi-scale environments [START_REF] Perlin | Pad: an alternative approach to the computer interface[END_REF], [START_REF] Bederson | Toolkit design for interactive structured graphics[END_REF], [START_REF] Pietriga | A Toolkit for Addressing HCI Issues in Visual Language Environments[END_REF], and those based on the walking and flying vehicle [START_REF] Ware | Exploration and virtual camera control in virtual three dimensional environments[END_REF] metaphors commonly employed to interactively explore 3D worlds. Beyond the now-ubiquitous map-like overviews introduced thirty years ago [START_REF] Donelson | Spatial management of information[END_REF], a variety of bifocal techniques termed focus+context have been designed to further help users navigate in complex visual representations such as large trees [START_REF] Lamping | A focus+context technique based on hyperbolic geometry for visualizing large hierarchies[END_REF], [START_REF] Munzner | Treejuxtaposer: scalable tree comparison using focus+context with guaranteed visibility[END_REF], graphs [START_REF] Gansner | Topological fisheye views for visualizing large graphs[END_REF], and high-resolution bitmap representations [START_REF] Carpendale | Achieving higher magnification in context[END_REF]. These techniques can also help users interact with objects in vector graphics editors [START_REF] Shoemaker | Supporting multi-point interaction in visual workspaces[END_REF] or select small interface widgets [START_REF] Ramos | Pointing lenses: facilitating stylus input through visualand motor-space magnification[END_REF]. The defining characteristic of these focus+context techniques is that they provide in-place magnification of a region (the focus) of the current display (the context), allowing users to get more detailed information about specific elements of the interface without having to zoom in the whole representation.

Interactive in-place magnification lenses have been available on the user's desktop for more than a decade, from simple magnifier lenses used as accessibility tools [START_REF] Blenkhorn | Screen magnifiers: Evolution and evaluation[END_REF] to fancy screen savers distorting the user's workspace. These early implementations were based on a simple magnification method that consisted in merely duplicating the pixels of the original representation.

While implementing such lenses is fairly trivial, implementing lenses that actually render objects in the magnified region with more detail is not. Models and implementations of the latter usually require information about, and some level of control on, the inner structure and elements of the representation, which might actually get modified by the lens. Such models and implementations are thus often tightly coupled with a particular graphics framework or application. From a purely theoretical perspective, however, the same general approach applies to many types of applications: 2D vector graphics editors, geographical information systems, CAD tools or any other 3D application. No matter the representation and underlying graphics framework, the process consists in rendering a subregion F of the current representation C at a larger scale and with more detail, and integrating F into C through a non-linear transformation to achieve a smooth transition between the two.

The Sigma Lens framework [START_REF] Pietriga | Sigma lenses: focus-context transitions combining space, time and translucence[END_REF] extends this general process by defining transitions between focus and context as a combination of dynamic displacement and compositing functions, making it possible to create a variety of lenses that use techniques other than spatial distortion to achieve smooth transitions between focus and context, and whose properties adapt to the users' actions, all in an effort to facilitate interaction. In this paper, we extend and strengthen that framework by describing a general approach to its design and implementation that shows how Sigma Lenses can be representation-independent. The main contribution is a rendering technique based on a unified model that can be integrated with minimal effort in different graphics frameworks, ranging from 3D graphics consisting of complex textured meshes to rich multi-scale 2D graphics combining text, bitmaps and After an overview of related work in Section 2, we give a theoretical description of our framework in Section 3, also summarizing the Sigma Lens unified model originally defined in [START_REF] Pietriga | Sigma lenses: focus-context transitions combining space, time and translucence[END_REF]. We then instantiate lenses of particular interest in this model, and present a series of evaluations that test their limit performance on 2D navigations tasks. We provide a detailed summary of the experiments reported in [START_REF] Pietriga | Sigma lenses: focus-context transitions combining space, time and translucence[END_REF], and report the results of a new controlled experiment that covers cognitive aspects of interaction with lenses that were left as future work, further confirming that one of our new lens designs, namely the SPEED-COUPLED BLENDING lens, significantly outperforms all others. A technical overview of two implementations follows, one for OpenGL 3D graphics taking advantage of hardware acceleration, the other for a general-purpose, cross-platform 2D application programming interface. Advantages and limitations of our approach are discussed in Section 8, along with plans for future work.

RELATED WORK

Many focus+context techniques are based on the concept of lenses. The simplest lens is the electronic equivalent of a magnifying glass. While easy to understand, this type of lens occludes the immediate surroundings of the magnified region [START_REF] Robertson | The document lens[END_REF], as a physical magnifying glass does, thus hiding an area of significant interest and making it difficult for users to relate focus and context in the representation. In order to avoid this problem, the magnified region is often integrated in the context using smooth transitions based on non-linear magnification techniques. These techniques create a transition zone in which the representation is distorted (see Figure 1-a).

Distortion-based visualization techniques often rely on metaphors inspired by the physical world such as stretchable rubber sheets [START_REF] Sarkar | Stretching the rubber sheet: a metaphor for viewing large layouts on small screens[END_REF] and, more generally, surface deformations [START_REF] Carpendale | 3-dimensional pliable surfaces: for the effective presentation of visual information[END_REF]. Others work with more fundamental concepts such as hyperbolic projection [START_REF] Lamping | A focus+context technique based on hyperbolic geometry for visualizing large hierarchies[END_REF] or non-linear magnification fields [START_REF] Keahey | Nonlinear magnification fields[END_REF]. The distortion can either extend to the limits of the representation [START_REF] Robertson | The document lens[END_REF], [START_REF] Sarkar | Stretching the rubber sheet: a metaphor for viewing large layouts on small screens[END_REF], or it can be bounded to a specific area. This paper focuses more specifically on the latter case, i.e., on lenses, termed constrained lenses [START_REF] Carpendale | Achieving higher magnification in context[END_REF], [START_REF] Keahey | Nonlinear magnification fields[END_REF], [START_REF] Carpendale | A framework for unifying presentation space[END_REF], [START_REF] Gutwin | Fisheyes are good for large steering tasks[END_REF], that leave a significant part of the context undistorted. Cockburn et al. [START_REF] Cockburn | A review of overview+detail, zooming, and focus+context interfaces[END_REF] survey many of these techniques in their recent review of overview+detail, zooming, and focus+context interfaces.

While all the above techniques apply to 2D graphics, other techniques have been developed for distortion in 3D. A first set of techniques deform 3D representations by projecting a texture on a mesh that models the distortion, as do pliable surfaces for 2D representations [START_REF] Carpendale | 3-dimensional pliable surfaces: for the effective presentation of visual information[END_REF]. LaMar et al.'s magnification lenses [START_REF] Lamar | A magnification lens for interactive volume visualization[END_REF] are based on homogeneous texture coordinates and special geometries. They can be applied to both 2D and 3D representations but are limited in the type of distortion and lens shapes they can model. Non-linear perspective projections [START_REF] Yang | Nonlinear Perspective Projections and Magic Lenses: 3D View Deformation[END_REF] project the RGB image produced by a 3D pipeline on a surface shape inserted in front of the flat projection plane. They can model spatially bounded distortions. Related to the latter is Brosz et al.'s single camera flexible projection framework [START_REF] Brosz | Single camera flexible projection[END_REF], which is capable of modeling non-linear projections through the parametric representation of the viewing volume.

There is also an impressive set of space deformation techniques (see [START_REF] Angelidis | Space deformations and their application to shape modeling[END_REF] for an overview), ranging from early works on the deformation of solid primitives [START_REF] Barr | Global and local deformations of solid primitives[END_REF], [START_REF] Sederberg | Free-form deformation of solid geometric models[END_REF] to view-dependent geometry [START_REF] Rademacher | View-dependent geometry[END_REF] and deformation based on hardware-accelerated displacement mapping [START_REF] Correa | Programmable shaders for deformation rendering[END_REF], [START_REF] Schein | Real-time geometric deformation displacement maps using programmable hardware[END_REF] and deflectors [START_REF] Kurzion | Interactive space deformation with hardware-assisted rendering[END_REF]. These techniques distort 3D geometry, but often do so in an object-centric manner, and are thus not well suited to the implementation of focus+context navigation lenses, which deform a region of the current display, i.e., a subsection of the current viewing frustum that intersects a set of objects, some of them only partially. Camera textures [START_REF] Spindler | Camera textures[END_REF] are among the few to actually apply constrained magnification lenses to 3D meshes, but the technique requires a sufficient level of tessellation of the target mesh to produce distortions of good quality.

Techniques such as the last one are typical examples of approaches strongly coupled with a specific type of graphics. This coupling is both a strength and a weakness. The strength lies in the capacity to access and modify the graphical objects that are to be distorted and rendered in a focus+context view. This is also a weakness, however, as a technique that works with 2D vector graphics will not be applicable to 3D meshes, or even to representations that include bitmap images. Other techniques, such as those based on 3D surface deformation and texture mapping, suffer from a somewhat opposite problem: while generating focus+context views of 2D representations, they require capabilities that are often not available in 2D graphics libraries.

One goal of our approach is to provide a method for implementing constrained magnification lenses that is as independent as possible of the nature of the representation and graphics library employed, ranging from 3D scenes in OpenGL to rich 2D vector graphics, as typically manipulated with tools such as Adobe Illustrator TM . Our other goal is to create a flexible framework of higher expressive power than existing solutions, going beyond distortion to achieve smooth visual transitions between focus and context, resulting in lenses that can be manipulated more efficiently by users.

GENERAL FRAMEWORK

Our general approach is positioned at a level of abstraction high enough for the model to be applicable to a variety of graphics frameworks, requiring the underlying libraries to provide as small a number of features as possible. It basically consists in transforming the representation at the pixel level after it has been rendered, independently of how it was rendered. To employ terminology drawn from 3D graphics, our technique works in image space, as opposed to object space. This approach has advantages beyond its wide applicability but also some limitations, which will be discussed later in Section 8.

Dual Rendering

All constrained magnification lenses featuring a regular shape share the following general properties, no matter how they transition between focus and context (see Figure 2):

• R I : the radius of the focus region (a.k.a the flat-top), which we call inner radius,

• R O : the radius of the lens at its base, i.e., its extent, which we call outer radius,

• M M : the magnification factor in the flat-top. Applying a constrained lens to a representation effectively splits the viewing window into two regions: the context region, which corresponds to the part of the representation that is not affected by the lens, and the lens region, in which the representation is transformed. We consider the lens and context regions as separate buffers: the context buffer holds what is displayed in the absence of any lens; the lens buffer contains a rendering of the region corresponding to the bounding box of the lens. These basically correspond to the context and focus viewing windows of the original Sigma Lens model [START_REF] Pietriga | Sigma lenses: focus-context transitions combining space, time and translucence[END_REF] in the case of 2D multi-scale representations, though here we are not limited to this type of graphics representation.

Our technique consists in asking the underlying graphics library for two separate rendering passes. One corresponds to what is seen in the context region and is stored in the context buffer, whose dimensions w × h match that of the final viewing window displayed to the user. The other rendering pass corresponds to what is seen in the lens region. Since we want the lens to actually provide a more detailed representation of objects in the magnified region, and not merely duplicate pixels from the previous rendering, the actual dimensions of the lens buffer are 2

• M M • R O × 2 • M M • R O .
The buffer can thus accommodate a uniform magnification by a factor of M M of the lens region. The final viewing window displayed on screen can then be obtained through the arbitrary transformation and composition of pixels from both buffers. This includes displacement and compositing functions that will control the transition between the focus and context regions, as defined in the Sigma Lens unified model [START_REF] Pietriga | Sigma lenses: focus-context transitions combining space, time and translucence[END_REF], which we briefly summarize.

Sigma Lenses

Sigma lenses build upon prior work on distortion lenses [START_REF] Carpendale | A framework for unifying presentation space[END_REF], but combine space, time and translucence to define new types of transitions between focus and context, in an effort to create more usable lenses (see Sections 5 and 6).

The standard transformation performed by graphical fisheyes consists in displacing all points in the focus buffer to achieve a smooth transition between focus and context through spatial distortion. This type of transformation can be defined through a drop-off function which models the magnification profile of the lens. The drop-off

Definition 1 : displacement and compositing function R R(x, y) =            (x c + x-xc M M , y c + y-yc M M ) α F T (x, y) {∀(x, y)|D(x, y) R I } (1.1) (x c + x-xc G scale (D(x,y)) , y c + y-yc G scale (D(x,y)) ) Gcomp(D(x,y)) (x, y) {∀(x, y)|R I < D(x, y) < R O } (1.2) (x, y) {∀(x, y)|D(x, y) R O } (1.3)
function is defined as:

G scale : d → s
where d is the distance from the center of the lens and s is a scaling factor. Distance d is obtained from an arbitrary distance function D. A Gaussian-like profile is often used to define drop-off function G scale , as it provides one of the smoothest visual transitions between focus and context (see Figures 2 and3). It can be replaced by other functions, which are already well-described in the literature [START_REF] Carpendale | Achieving higher magnification in context[END_REF], [START_REF] Carpendale | A framework for unifying presentation space[END_REF]. Distance functions producing basic regular lens shapes are easily obtained through L(P )-metrics [START_REF] Carpendale | A framework for unifying presentation space[END_REF]:

D : (x, y) → P |x -x c | P + |y -y c | P
where (x, y) are the coordinates of a point seen through a lens centered in (x c , y c ), and P ∈ N * . P = 2 corresponds to a circular lens and P = ∞ to a square lens. As discussed later, more complex or irregular lens shapes can easily be obtained, e.g., by making R I and R O angledependent, usually in combination with L(2).

In our approach, the overall process consists in applying a displacement function to all pixels in the lens buffer that fall into the transition zone: pixels between R I and M M •R O get compressed according to the dropoff function in such a way that they eventually all fit between R I and R O . Pixels of the lens buffer can then be composited with those of the context buffer that fall into the lens region.

When only interested in spatial distortion, generating the final representation simply consists in replacing pixels in the lens region of the context buffer by those of the lens buffer; in other words compositing them with the over operator (α = 1.0). But other values of α and other operators in Porter & Duff's rich algebra [START_REF] Porter | Compositing digital images[END_REF] can be used to achieve interesting visual effects. It is for instance possible to obtain smooth, distortionfree transitions between focus and context by applying an alpha blending gradient centered on the lens. Or, as we will see later, a simple magnifier lens (R I = R O ) can be made much more usable by making it uniformly translucent and coupling α to its speed.

The rendering of a point denotes the pixel resulting from alpha blending a pixel from the lens buffer and another from the context buffer with an alpha value of α. As with scale for distortion lenses, the alpha blending gradient can be defined by a drop-off function that maps a translucence level to a point (x, y) located at a distance d from the lens center:

G comp : d → α
where α is an alpha blending value in [0, α F T ], α F T being the translucence level used in the flat-top of the lens.

The flat-top region corresponds to case (1.1) of Definition 1, the transition to case (1.2), and the region beyond the lens boundaries, i.e., the context, corresponds to case (1.3). Detailed information about the model and functions summarized in this section can be found in the original paper on Sigma Lenses [START_REF] Pietriga | Sigma lenses: focus-context transitions combining space, time and translucence[END_REF].

INSTANTIATING LENSES IN THE MODEL

In our approach to the implementation of the Sigma Lens framework, new lenses are obtained very easily, only by defining functions G scale and G comp . Some examples of interesting transitions follow.

First, for reference, a plain and simple distortion lens with a Gaussian-like drop-off function (Figure 3) can simply be obtained with the following instantiations of G scale and G comp :

{∀d|R I < d < R O } G scale (d) = M M -1 • cos( π R O -R I • d -π•R I R O -R I ) + M M +1 2 G comp (d) = 1.0 Figures 1-a and 2
give examples of a distortion lens with a Gaussian-like drop-off.

The BLENDING lens described in [START_REF] Pietriga | Sigma lenses: focus-context transitions combining space, time and translucence[END_REF], which achieves a smooth transition between focus and context through gradual alpha blending only (Figure 4), is easily instantiated using a linear drop-off for α:

{∀d|R I < d < R O } G scale (d) = M M G comp (d) = α F T R I -R O • d -α F T •R O R I -R O
This type of lens does not feature a continuous spatial transition between focus and context. Instead, visual continuity is achieved through increasing translucence.

As with any lens, other distance functions can be used [START_REF] Carpendale | A framework for unifying presentation space[END_REF]. L(∞), however, introduces artificial edges which give a false impression of spatial depth; if a square lens is required, L(3) offers an interesting approximation, smoothing the edges while featuring a shape close to a square, as illustrated in Figure 5.

Spatial distortion and gradual alpha blending can of course be combined. Figure 6 shows an example of a so-called HOVERING lens as it appears to float above the representation.

{∀d|R I < d < R O } G scale (d) = 1-M M R O -R I • d + M M •R O -R I R O -R I G comp (d) = α F T R I -R O • d -α F T •R O R I -R O
This lens mitigates issues of both distortion-only and alpha blending-only transitions: i) when the user is performing a focus targeting action 1 , the target object no longer appears to temporarily move away from the approaching flat-top when entering the peripheral zone of the transition region (an effect due to the spatial distortion) as this zone is almost transparent; ii) this peripheral zone is still visible (undistorted) by translucence through the inner, distorted zone of the transition; iii) the distortion in this inner region contributes to visually differentiating focus and context during lens movements, and to the minimization of the distance between the point where an object disappears from the context and the point where it appears in the focus area.

Speed-coupling

In addition to the transition functions described earlier, the Sigma Lens framework allows for lens properties such as magnification factor, radius or flat-top opacity 1. The low-level and ubiquitous action which consists in moving the lens in the main window so as to position it over an object to be magnified in the flat-top is termed focus targeting [START_REF] Gutwin | Improving focus targeting in interactive fisheye views[END_REF]. to vary over time. The first example of lens to make use of dynamic properties was Gutwin's SPEED-COUPLED FLATTENING lens [START_REF] Gutwin | Improving focus targeting in interactive fisheye views[END_REF], which uses the lens' dynamics (velocity and acceleration) to automatically control magnification. By canceling distortion during focus targeting, speed-coupled flattening lenses improve the usability of distortion lenses. Basically, M M decreases toward 1.0 as the speed of the lens (operated by the user) increases, therefore flattening the lens into the context, and increases back to its original value as the lens comes to a full stop. Such behavior can easily be implemented in our approach using a simple interpolated low-pass filter (see [START_REF] Pietriga | Sigma lenses: focus-context transitions combining space, time and translucence[END_REF] for detailed information). Let S(t) be the time-based function returning a numerical value that depends on the velocity and acceleration of the lens over time. The function is set to return a real value in [0.0, 1.0]. Making a lens parameter such as the magnification factor M M speed-dependent is then easily achieved by simply multiplying that parameter by the value of S(t), as shown in Figure 7-a.

Other properties can be made speed-dependent, including the radii R I and R O , as well as the translucence value in the lens' flat-top α F T . For instance, the SPEED-COUPLED BLENDING lens, which to our knowledge features the best focus targeting performance, is also easily obtained as shown in Figure 7-b. This lens features a larger flat-top area compared to lenses of the same size that feature a transition zone. This makes the earliermentioned focus targeting task easier for the user from a purely motor perspective, but the occlusion stemming from the absence of a smooth transition zone counterbalances this theoretical advantage. The occlusion problem (a) Speed-coupled Flattening Lens

R I R O R I R O 1.0 1.0 MM 0 0 d d scale α S(t) M M → 1 + (M M -1) • S(t) (b) Speed-coupled Blending Lens R I R O R I R O 1.0 1.0 MM 0 0 d d scale α S(t) α F T → α F T • S(t)
Fig. 7. Lenses with speed-coupled properties is addressed by coupling α F T to the speed of the lens: the lens becomes increasingly translucent as it is moved faster, and conversely (see Section 5 for more detail).

USER STUDY: FOCUS TARGETING PERFOR-MANCE

In order to verify the above assumptions about the properties of various lenses and their impact on user performance, we ran a series of experiments that evaluate lens usability in different navigation situations. We briefly present in this section the results of studies reported in detail in [START_REF] Pietriga | Sigma lenses: focus-context transitions combining space, time and translucence[END_REF], that compare a set of lenses on an elementary action involved in any navigation task: focus targeting. The task consists in putting a given target in the flat-top of the lens and is one of the building blocks of many higher-level navigation tasks such as searching [START_REF] Pietriga | Pointing and Beyond: an Operationalization and Preliminary Evaluation of Multi-scale Searching[END_REF]. We then report in Section 6 the results of new experiments that further test the two most efficient lenses in a more complex navigation task that involves both global and local navigation actions.

Apparatus

In all our experiments, we used a Dell Precision 380 equipped with a 3 GHz Pentium D processor, an NVidia Quadro FX4500 graphics card, a 1600 x 1200 LCD monitor (21") and a Dell optical mouse. The program was written with the multi-scale 2D framework presented in Section 7.1 . The application was limited to a 1400 x 1000 window with a black padding of 100 pixels in order to accommodate instruction messages.

Task and Procedure

Our focus targeting task consisted in acquiring a target in the flat-top of the lens as quickly as possible. In our experimental setting, the lens was centered on the mouse cursor. The task ended when the participant clicked the left mouse button, provided that the target was fully contained within the flat-top. Each trial consisted in performing 24 successive focus targeting tasks in a row. As illustrated in Figure 8, the targets were laid out in a circular manner. The order of appearance forced participants to perform focus targeting tasks in every direction, as recommended by the ISO9241-9 standard [START_REF] Iso | 9241-9 Ergonomic requirements for office work with visual display terminals (VDTs)-Part 9: Requirements for non-keyboard input devices[END_REF]. We decided to have only one target visible at a time, as we noticed during a pilot experiment in which all targets were visible that some participants were often taking advantage of the layout pattern to acquire the current target object by positioning the lens relative to that object's neighbors.

Experiment 1: Lens type and focus targeting

We first compared the focus targeting performance and limits of five lenses described earlier: a plain MAG- NIFYING GLASS, a simple distortion lens (FISHEYE), and BLENDING, SPEED-COUPLED FLATTENING, SPEED-COUPLED BLENDING (see Section 4). Focus targeting performance was evaluated at five different magnification factors (M M ). Higher magnification factors make the task increasingly difficult: (i) the transition area becomes harder to understand as it must integrate a larger part of the world in the same rendering area, and (ii) it becomes harder to precisely position the target in the flat-top of the lens, the latter being controlled in the motor space of the context window. To test the limits of each lens, we included factors up to 14x. Our experiment was a 5 × 5 within-participant design: each participant had to perform several trials using each of the five lenses with five different magnification factors (M M ∈ {2, 4, 6, 10, 14}).

Ten volunteers (7 male, 3 female), from 23 to 40 year-old (average 26.4, median 25), all with normal or corrected to normal vision, served in the experiment and allowed us to collect data on 11,500 actual focus targeting tasks.

v u O s s • MM Context viewing window W target W focus W lens = 2•R O D W focus W target ID = log 2 ( + 1) D 2•R I (1)
Fig. 9. Focus Targeting Task in a space scale diagram.

Results

Interestingly FISHEYE and BLENDING do not significantly differ in their performance. We initially thought that translucence could improve user performance by eliminating the space-based transition drawbacks. Transitioning through space indeed introduces distortion that makes objects move away from the approaching lens focus before moving toward it very fast, making focus targeting difficult [START_REF] Gutwin | Improving focus targeting in interactive fisheye views[END_REF]. BLENDING does not actually overcome this problem since it introduces a new one: the high cognitive effort required to comprehend transitions based on gradually increasing translucence which, as opposed to distortion-based transitions, do not rely on a familiar physical metaphor.

We expected speed-based lenses (SPEED-COUPLED FLAT- TENING and SPEED-COUPLED BLENDING) to outperform their static versions (FISHEYE and MAGNIFYING GLASS). Each focus targeting task can be divided into two phases: in the first phase, the user moves the lens quickly to reach the target's vicinity, while in the second phase, she moves it slowly to precisely position the target in the focus. In the first phase, the user is not interested in, and can actually be distracted by, information provided in the focus region since she is trying to reach a distant object in the context as quick as possible. By smoothly and automatically neutralizing the focus and transition regions during this phase, and then restoring them, speed-based lenses should help the user. Our results did actually support that this is the case for SPEED-COUPLED BLENDING and MAGNIFYING GLASS: smoothly neutralizing and restoring the focus of a MAGNIFYING GLASS by making it translucent does improve performance. However our participants were not significantly faster with SPEED-COUPLED FLATTENING than with FISHEYE. This was especially surprising since the study conducted in [START_REF] Gutwin | Improving focus targeting in interactive fisheye views[END_REF] showed a significant improvement in users performance with SPEED-COUPLED FLATTENING. We think this inconsistency is probably due to implementation differences: we implemented SPEED-COUPLED FLATTENING as a constrained lens while it was implemented as a full-screen lens by Gutwin. In full-screen lenses, distortion affects the whole representation, which thus benefits more from the neutralization effect than constrained lenses that only affect a limited area. From a pure motor perspective, the difficulty of a focus targeting task can be evaluated as a view pointing task in a fixed-scale interface [START_REF] Guiard | Target acquisition in multiscale electronic worlds[END_REF]. We can thus use Formula (1) in Figure 9 to quantify the difficulty of moving the lens' flat-top, of size W f ocus , to a position where it will contain the target, of size W target , initially located at a distance D from the lens' center. Formula (1) computes the Index of Difficulty, ID, of our focus targeting task. The lens' position in the context window is controlled in the visual and motor space of that window. W target , W f ocus and D are thus expressed in context pixels: in our experiment, W target = 8 pixels and D = 800 pixels, while W f ocus depends on a given Lens × M M condition: W f ocus = (2 × R I )/M M . As M M increases, the size of W f ocus decreases, making the task more difficult. For lenses of equal size (R O ), the size of the flat-top (R I ), and thus W f ocus , vary depending on the lens type. MAGNIFYING GLASS and SPEED-COUPLED BLENDING lenses are made of a flat-top only: W f ocus = W lens = 200, while other lenses have to accommodate the transition within the same overall area: W f ocus = W lens /2 = 100 in our implementation. MAGNIFYING GLASS and SPEED-COUPLED BLENDING thus feature a larger flat-top than other lenses with the same overall size, consequently making focus targeting easier from a motor perspective: ID ranges from 3.2 to 6.3 for MAGNIFYING GLASS and SPEED-COUPLED BLENDING while it ranges from 4.2 to 8 for FISHEYE, SPEED-COUPLED FLATTENING and BLENDING. Our data showed that SPEED-COUPLED BLENDING is actually faster than all other lenses starting at M M = 4. However MAGNIFYING GLASS becomes the worst lens at M M = 6: its large opaque flat-top causes occlusion that makes the second phase of the task (precise positioning) too difficult to make users benefit from a larger flat-top.

Figure 10 summarizes these results. Our analyses only provide a partial order of performance between the five lenses but strongly support that SPEED-COUPLED BLEND- ING lens is the most efficient lens.

Experiment 2: Flat top size and focus targeting

Experiment 1 compared lenses with the same size (R O ). We found that SPEED-COUPLED BLENDING lenses outperform SPEED-COUPLED FLATTENING lenses, and attributed this performance gain (i) to the large flat-top of the SPEED-COUPLED BLENDING lens, which makes focus targeting easier from a motor perspective, and (ii) to the absence of distortion and reduction of occlusion effects through the coupling of focus translucence with lens speed. Experiment 2 aimed at better understanding the results of the previous experiment by identifying the contribution of both properties to this performance gain. We studied how SPEED-COUPLED BLENDING performed at two "extreme" sizes: 1) the lens has the same size as other lenses (W lens = 200), and 2) the lens has the same size as the flat-top of lenses which accommodate a transition area and thus feature a smaller flat-top (W lens = 100), making focus targeting harder from a motor perspective as explained earlier. We called the latter SPEED-COUPLED BLENDING small and compared it to SPEED-COUPLED BLENDING and SPEED-COUPLED FLATTEN-ING, both from the previous experiment. Two representative magnification factors were selected: M M ∈ {8, 12}. This experiment was thus a 3 × 2 within-participant design. Six volunteers (5 male, 1 female), from 23 to 40 year-old (average 27.8, median 25.5), all with normal or corrected to normal vision, served in the experiment. Figure 11 illustrates our results: even at the same level of motor difficulty, the SPEED-COUPLED BLENDING lens still performs better than the SPEED-COUPLED FLATTENING lens. This means that interface designers are given several options to improve upon a classical lens such as FISHEYE: 1) they can either get a smaller but more efficient lens (in terms of focus targeting performance), saving screen real-estate for the context, 2) if the latter is not critical they can make the SPEED-COUPLED BLENDING lens occupy the same space as a FISHEYE would, further improving focus targeting performance, or 3) find a balance between these solutions.

EXPERIMENT 3: TRANSLUCENCE AND

SPEED-DEPENDENCE

Lieberman used translucence in Powers of Ten Thousands [START_REF] Lieberman | Powers of ten thousand: navigating in large information spaces[END_REF], a bifocal display technique that makes the focus and context views share the same physical screen space, by using multiple translucent layers. Even though it has been shown to be usable in exploratory studies [START_REF] Cox | The usability of transparent overview layers[END_REF], [START_REF] Harrison | Transparent layered user interfaces: an evaluation of a display design to enhance focused and divided attention[END_REF], this type of representation based on transparent or translucent layers is cognitively demanding, causing visual interferences that are the source of serious legibility problems, and requiring additional mental effort from the user to relate focus and context. Translucence can hence affect targeting performance, especially when targets are superimposed on a complex background such as a map or photograph. Speed-dependent properties can also be confusing as they affect the lens' appearance depending on cursor movements. As the simple abstract world we used in the first two experiments might have hidden potential negative effects caused by translucence, we present here further controlled experiments aimed at verifying that our comparative lens performance ordering is still valid in more realistic environments.

Preliminary experiment

In [START_REF] Pietriga | Sigma lenses: focus-context transitions combining space, time and translucence[END_REF], we had already conducted a preliminary study to assess the potential effects of translucence on targeting performance. The task was the same as described earlier, but the 24 targets were laid out on a satellite photograph, and could either be filled with a fully opaque red color or with a translucent red, in which case they blended into the background and were less easily identifiable. The satellite photograph was a 7000×5000 pixels portion of NASA's Blue Marble world map [START_REF] Stockli | The Blue Marble Next Generation -A true color earth dataset including seasonal dynamics from MODIS[END_REF], providing an appropriate level of detail in both the focus and context regions. This experiment yielded a performance ordering consistent with that observed in the first two. Target opacity had a significant effect on performance only for BLENDING. This result is not unexpected as the BLEND-ING lens can be prone to visual interference between focus and context in the transition region depending on the nature of the representation, especially when non-contrasted objects are targeted. No matter how aesthetically pleasing (several participants noted that it produced very nice graphical renderings), the BLENDING lens suffers from a lack of reliance on a familiar physical metaphor, and proneness to visual interference in the transition region. The SPEED-COUPLED BLENDING lens, however, does not seem to suffer from these problems, as its use of translucence is very different: it can be seen as a magnifying glass whose content smoothly fades out to prevent occlusion at focus targeting time.

In the remainder of this section, we further evaluate speed-dependent lenses by introducing a task that implies more speed variations when operating the lens by forcing both global navigation (large movement followed by a stop) and local navigation (small movements for fine-grain positioning), as the preliminary experiment described above suggests that SPEED-COUPLED BLENDING could cause some legibility problems since it is neither opaque nor fully transparent during local navigation phases.

Task and procedure

Transitions based on distortion or transparency add complexity to the representation, and can affect usability differently depending on the nature of the objects displayed. To test lens usability in a wide range of realistic situations, we used different representations. We conducted two experiments illustrated in Figure 12 based on two different types of representation: a network (vector graphics) for Experiment 4 graph (Bg = graph), and a high-resolution satellite map (bitmap) for Experiment 4 map (Bg = map). In both cases, the task is the same. A word is displayed to the user in three locations: top, center and bottom of the screen. Participants are instructed to memorize this word as they will have to search for it in the representation. Once this target word is memorized, participants put the cursor on a red square (20 × 20 pixels) located at the center of the screen and press the space bar to start the trial. The red square disappears, as does the target word displayed at the center (the ones displayed in the top and bottom margins remain displayed throughout the trial in case participants forget it). Words appear successively in the same locations as the circular targets did in previous experiments. When a word appears, the participant has to move the lens over it to be able to read it (a word represents about 27 × 8 pixels in the context and is thus unreadable at this scale). If the word is not the target word, she proceeds to the next one by pressing the space bar. This is repeated until she finds the target word, in which case she clicks the left mouse button to end the current trial and start a new one.

In both cases (mouse click or space bar), the word must be in focus. For a word to be considered in focus, our software uses the following criterion: the intersection area between the word and the lens' flat-top should be at least 66% of the flat-top area (thus ensuring that the word can be read). A word can however never be fully displayed in the flat-top. This is to force participants to perform local navigation as described earlier. Here again to compare lenses both in usual and extreme conditions, we use two magnification factors (M M ∈ {8, 12}). Font size is set to 42 pts (at context scale) for M M = 8 and 28 pts for M M = 12, so that the lens' flat-top can display at most 6 letters at full magnification. We use two word lengths to test the effect of the amount of local navigation Fig. 13. Exp. 4 map : Opaque target vs. Translucent target on lens performance (LabLength ∈ {8, 12}). To decrease the probability of a participant recognizing a word only based on a few specific letters (which would reduce the amount of local navigation), we have chosen words that are similar to a certain degree: all 8-letter words start with 'a' and end by 'ed'; all 12-letter words start with 'm' and end by 'ed'. We also had to make participants believe that the target word could appear at any time so they don't turn the task into a pure routine motor task.

To that end, we introduced a secondary factor, Rank, that was used to control how many objects participants had to inspect before finding the target word for a given trial. Rank could take four different values: {2, 4, 6, 8}.

The graph of Experiment 4 graph contained 76 nodes that were laid out in a semi-random manner so as to provide a uniform density and to make sure that a node would coincide with each of the potential target locations (a word was always displayed inside a node -see Figure 12-a). For Experiment 4 map , we used the NASA world map mentioned earlier (Figure 12-b). In this latter experiment, we introduced an additional factor: in half of the trials, words were opaque (O) while in the other half, they were translucent 2 (T ) (Opacity ∈ {O, T }), as shown in Figure 13. We hypothesized that background and focus might be perceptually interpreted as one illegible image if contrast is not strong enough, especially for SPEED-COUPLED BLENDING as it itself makes use of translucence. Opacity was not included as a factor in Experiment 4 graph because sharp edges displayed on a uniform background are strongly contrasted.

Twelve volunteers (9 male, 3 female), from 23-33 years (avg. 26.7, med. 26.5), all with normal or corrected to normal vision, no color blindness, served in the experiment. Each of them was involved in both experiments. Experiment 4 graph lasted around 40 minutes, 4 map lasted around 1 hour (instructions were shorter since all participants were already familiar with the task). The two experiments were performed on two different days to minimize fatigue and boredom. Each experiment was composed of four blocks, one per Lens×M M condition. Successive changes of Lens values would have been too disturbing. To counterbalance Lens presentation order, 6 participants saw the 2 SPEED-COUPLED FLATTENING blocks first, while the 6 other participants started with SPEED- COUPLED BLENDING. We always presented block M M = 8 first for a given Lens, so as to avoid harder conditions being presented first to participants.

A Lens × M M block contained 4 series of 4 trials in 2. When Opacity = T , words and their black background are rendered with an alpha channel set to 0.2, thus blending into the satellite image, which makes them more difficult to identify (Figure 13).

Exp. A series contained words of the same length and presented the four different Rank values in a pseudorandom order to ensure that the overall difficulty was the same for all participants. In Experiment 4 graph , a participant saw alternatively a series of 8-letter words and a series of 12-letter words, twice. In Experiment 4 map , a participant saw alternatively two series of 8-letter words and two series of 12-letter words, twice; one series per opacity value (Opacity = O then Opacity = T ). Table 1 summarizes this experimental design.

Results and Discussion

We collected three main measures for our analyses: (i) completion T ime, i.e., the time interval between the appearance of the first word and the click on the target word; (ii) the number of Reading errors, i.e., when the participant notices that she has pressed the space bar instead of clicking on the target word or if she has visited an abnormally large number of words 3 ; (iii) the number of Acquisition errors, i.e., when the participant presses the space bar or clicks while the word is not in focus. In this case, the message "target not in focus" would flash and the participant would have to adjust the lens (the trial continues, the timer is not reset).

A total of 62 trials among 768 were restarted because of Reading errors in Experiment 4 graph (∼ 8%) and 128 trials among 1536 in Experiment 4 map (∼ 9%). Note that the recorded time for these particular trials was potentially biased, as participants could avoid some cognitive aspects of the task and turn it into a simple motor task. For instance, if a participant remembered the rank at which the target word appeared when realizing her failure, she could avoid having to carefully read the intermediary words the second time, simply pointing at them. To avoid analyzing data with an unbalanced number of measures per factor, we left these trials in our data after having checked that (i) Reading errors were uniformly distributed among the primary factors and (ii) that neither primary factors nor Rank had a significant effect on the number of Reading errors.

3. Instructors told participants that if they had visited about 15 words without having seen the target word this meant they had missed it. In this case, the participants could press the Escape key to skip the current trial and restart it (the timer was reset).

TABLE 2

Significant effects revealed by analysis of variance of M M and Lens factors on Acquisition errors Figures 14-a to 14-h show the data collected along the Lens, M M and LabLength factors. Regarding T ime, we did not observe any significant effect of any condition. We can see in the first two columns that participants were faster using SPEED-COUPLED BLENDING than SPEED-COUPLED FLATTENING. This difference was however not statistically significant.

Differences in accuracy were stronger. In both experiments, participants were more accurate using SPEED- COUPLED BLENDING than SPEED-COUPLED FLATTENING.

Lens and M M had a significant effect on both T ime and Acquisition errors (Table 2). Furthermore, differences between lenses in terms of accuracy increased with the magnification factor (Figures 14-c and 14-d): Lens × M M had a significant effect on Acquisition errors.

Participants were more accurate with shorter words: LabLength had a significant effect on Acquisition errors in Experiment 4 map (F 1,11 = 22, p < .0001), see Figure 14-h. However, participants were not significantly faster with shorter words. We did not expect this observation since the task is supposed to be harder from a motor perspective. The local navigation required by longer words probably penalizes overall task performance more than the motor aspects involved in a simple focus targeting task. In addition, lenses seem to be unequally affected by word length: Lens × LabLength was significant on Acquisition errors (F 1,11 = 17, p < .0001) in Experiment 4 map . These results tend to show that SPEED-COUPLED BLENDING better supports local navigation than SPEED-COUPLED FLATTENING (Figures 14-f and14-h). This latter effect, observed only in Experiment 4 map , reinforces our intuition that lens usability is affected by the type of representation. To have a closer look at this effect, we built a table resulting from the concatenation of trials of Experiment 4 graph (Bg = Graph) and trials where Opacity = O of Experiment 4 map (Bg = M ap). Analysis of variance revealed a significant effect of Bg on Acquisition errors (F 1,11 = 17, p < .0001) but not on T ime (Figure 14-i and 14-j). Participants were more accurate on a vectorbased representation (the network) probably because the white background helped perceive the limits of the label. We also found one interaction effect Lens × Bg on Acquisition errors (F 1,11 = 14, p = 0.0002): surprisingly SPEED-COUPLED FLATTENING is more penalized by background type than SPEED-COUPLED BLENDING is (left of Figure 14-j). Transparency does not hinder performance on complex representations, and seems more robust than distortion for high magnification factors. Hence, our hypotheses about usability problems due to the use of transparency are not supported by this experiment. Analysis of the Opacity factor in Experiment 4 map also supports SPEED-COUPLED BLENDING's robustness. The effect of Opacity on Acquisition errors was significant (F 1,11 = 6, p = 0.01), which is consistent with participants remarks about the reading difficulty they had when labels were translucent. Interaction effect Lens × Opacity was also significant on Acquisition errors (F 1,11 = 5, p = 0.02) revealing that users were more strongly affected by label opacity with SPEED-COUPLED FLATTENING than with SPEED-COUPLED BLENDING. As a summary, speed-coupled translucence does not have a negative impact on reading performance. The dynamically varying translucence of the SPEED-COUPLED BLEND- ING lens does not cause significant visual interference, even on complex scenes featuring a low level of contrast. The SPEED-COUPLED BLENDING lens remains more efficient than the SPEED-COUPLED FLATTENING lens.

IMPLEMENTATIONS

According to the previous evaluations, Sigma Lenses should prove useful in various types of graphical user interfaces. The next step consists in investigating how to add support for the framework in existing graphics environments. Though implementation is not straightforward, the approach is generic enough that it can be implemented in different environments with only a few requirements. The underlying graphics library must allow i) for the scene to be rendered at different levels of detail, and ii) for the pixels that constitute the two rendered images (the context region and the lens region) to be manipulated and composited before the actual rendering to the screen occurs. The following sections describe two different implementations, one for multiscale 2D graphics, the other for OpenGL scenes.

Multi-scale 2D Framework

Pad [START_REF] Perlin | Pad: an alternative approach to the computer interface[END_REF] was one of the first toolkits designed for the implementation of multi-scale interfaces. Since then, several other zoomable user interface toolkits have been developed, including Piccolo [START_REF] Bederson | Toolkit design for interactive structured graphics[END_REF] and ZVTM [START_REF] Pietriga | A Toolkit for Addressing HCI Issues in Visual Language Environments[END_REF]. Our implementation is based on the latter, an open source toolkit built on top of Java2D. It allows for the same scene to be rendered from different viewpoints. Furthermore, as the toolkit does not rely on Java's internal double buffering mechanism but implements its own and makes the offscreen rendering buffers publicly accessible, adding support for Sigma Lenses was easy. Our extension works directly on these offscreen images, and is independent of their content. It is thus readily compatible with all graphical objects that can be displayed by the toolkit, including arbitrary vector-based shapes, bitmap images and text rendered with any font.

A call to the extension is simply inserted in the rendering loop, between the rendering of the main offscreen buffer, which corresponds to the context region, and its copy to the screen. The extension asks for a second rendering from the viewpoint of a camera set to observe the lens region. Clipping algorithms internal to the toolkit make sure that only objects visible through each camera get projected and drawn in the associated offscreen buffer. Our extension then creates the focus+context representation. As a significant part of the final rendering will match the context buffer exactly, the latter serves as the target of the transformation to prevent unnecessary copy operations. For each pixel (x, y) in the subregion corresponding to the lens, we simply read a pixel in the raster associated with the lens buffer using an index computed through function R, thus achieving magnification as well as distortion depending on the drop-off defined by G scale . This pixel gets composited with the original pixel (x, y) from the context buffer, using alpha blending if necessary with a value of α computed through function R (more specifically G comp ). Pixels outside the lens region are left untouched.

The core classes of the extension represent about 700 lines of actual code, supporting three different BufferedImage types (type varies depending on operating system and color depth). Taking advantage of the inheritance mechanism, a new lens is then typically written with less than 100 lines of code: most of those lines are dedicated to constructors, getters, and setters. Lines that actually modify the rendering of the transition, i.e., implementations of G scale and G comp specific to each lens, only account for about 10% of those 100 lines except for lenses with speed-dependent properties, in which case the coupling with the interpolated low-pass filter adds an extra 80 lines of code.

Performance. We measured the performance of this implementation on a representation consisting of a multi-scale version of the high-resolution (86400 × 43200 pixels) Blue Marble Next Generation world map from NASA [START_REF] Stockli | The Blue Marble Next Generation -A true color earth dataset including seasonal dynamics from MODIS[END_REF]. The pyramid consists of 2,728 tiles, each 1350 × 1350 pixels in size. We overlaid shapefile data representing country boundaries as vector graphics on top of the map, amounting to 23,715 segments forming 1,375 polygons of various shapes and sizes. Performance tests were run on a Windows XP PC, equipped with a 3 GHz Pentium D processor, 2 GB of RAM and an NVIDIA Quadro FX 4500 graphics card with 512 MB of memory, using Java 1.6 with the default DirectX rendering pipeline enabled. The application ran in a 1280 × 640 window. All lenses were 200px wide, occupying about 5% of the rendering area, and were tested at various magnification factors ranging from 2x to 8x. Rendering the content of the context buffer took an average of 23ms (base condition). Average time spent rendering and compositing the content of the lens buffer ranged from 24ms in the best case (2x distortion lens) to 74ms in the worst case (8x hovering lens), corresponding to overall frame rates varying between 21fps and 10fps. While not extremely high, the measured frame rates show that our framework can be implemented in graphics environments that do not benefit from significant hardware acceleration such as plain Java2D, and still achieve interactive frame rates for relatively complex representations.

3D Framework

The second implementation takes advantage of programmable graphics hardware. Lenses are written with the OpenGL Shading Language (GLSL). The rendering process is as follows. First, the lens region is rendered to a texture, thanks to a framebuffer object that makes it possible to render to other destinations than those provided by the window system. The projection frustum is set to match the lens region, so that only objects visible in that region get rendered in this first pass. Only the projection frustum is changed, not the camera position, so as not to introduce any discontinuity between the context and lens regions. The viewport's dimensions, and thus those of the target texture are set 4 according to the lens buffer's size:

2 • M M • R O × 2 • M M • R O .
Second, the viewport and perspective projections are set according to the dimensions of the application's window to render the scene as it would look like in the absence of any lens. Third, the texture generated during the first step is mapped on a plane matching the lens region using normalized texture coordinates. If the scene were to be rendered through the standard fixed function pipeline, this higher-resolution texture would perfectly blend into the context. Instead, we use a fragment shader that implements the lens' displacement and compositing functions. The data contained in the texture is accessed through this fragment shader. Context fragment color data is accessed from the lens texture through a texture sampler by using the texel coordinates calculated by the standard fixed function pipeline in previous stages of the rendering process: The fragment shader is independent of the content of the scene observed. It is an implementation of the specific instance of function R defining one particular lens, nothing more. External data controlled by the application, such as the position of the lens (x c , y c ), its magnification factor M M , or the cursor speed, are sent to the shader using GLSL uniform variables. The source code of a standalone shader is thus very small, typically 60 to 80 lines, instructions related to a specific instance of G scale or G comp typically amounting to two to four lines.

Performance. We used the same hardware configuration as in the 2D implementation section, except that the software was running under Linux, with version 169.07 of the NVIDIA driver. The application ran in a 1050 × 750 window and displayed 3D objects of varying complexity. We tested lenses 200px to 800px wide, at magnification factors ranging from 2x to 8x. Measures indicate that, in these ranges, the values of M M and R O have negligible influence on performance. In all cases, rendering the content of the lens region takes approximately the same amount of time as rendering the context in the frame buffer. For instance, a 3D model made of 69,451 facets is displayed at 123fps with a lens vs. 231fps with no lens; another model made of 345,944 facets 4. If the dimensions exceed the maximum texture size permitted by the graphics card, the lens region can be rendered in smaller tiles that are then read using the multi-texture access capabilities of fragment shaders.

is displayed at 28fps vs. 53fps. Performance could be improved if necessary by implementing manual frustum culling, taking the different sizes of the context and lens regions into account (lens rendering time would depend on the lens region's dimensions). Time spent distorting and compositing in the fragment shader is not significant compared to scene rendering time.

DISCUSSION AND FUTURE WORK

As opposed to most techniques described in the literature, we wanted to develop a lightweight, representation-independent approach to the problem of focus+context navigation based on constrained lenses. This choice has implications in terms of implementation effort, expressive power and graphics performance.

Graphics performance will obviously vary depending on the complexity of the representation and on the underlying graphics framework's capabilities, such as clipping algorithms and level of support for hardware acceleration; but even in cases where most of the computations are done on the software side, acceptable frame rates can be achieved for most lenses on reasonably complex scenes such as the one described in Section 7.1. Performance can however be an issue when highly magnifying lenses defined by complex drop-off functions for both scale and translucence are used in a non hardware-accelerated framework. In that case, values for G scale (displacement function) and G comp (blending gradient) can be pre-computed for each target pixel in the lens region and stored in a data structure such as an array or texture for fast lookup. Memory consumption will amount to a maximum of two structures storing (2R O ) 2 floating point numbers, and can be lowered to a quarter of that value by taking advantage of vertical and horizontal symmetry for lenses based on L(P )-metrics.

The shape of a lens does not necessarily have to feature the above-mentioned symmetry. While most constrained lenses have been restricted to regular shapes such as circles and squares (Magic Lenses [START_REF] Bier | Toolglass and magic lenses: the see-through interface[END_REF] excepted), irregular perimeters can be obtained fairly easily by defining them using parametric equations that make R I and R O angle-dependent. We are planning to better integrate such perimeters in the framework, our final goal being to build adaptive lenses whose shape changes to provide more relevant magnifications of the objects in focus by accessing information about their geometry.

One strong point of our approach is its good expressive power which comes at a relatively small implementation cost. The two implementations described in Section 7 show that it can be implemented with minimal effort in various graphics frameworks, only requiring offscreen drawing capabilities, a feature commonly available in graphics APIs, and the possibility to draw the representation at two different scales. Once the core lens programming elements are in place (when required at all), writing a new lens typically takes only a few lines, most of the code being the same from one lens to another, and differences residing mainly in the definition of transitions.

Working on the rendered scene, distorting and compositing the focus and context regions by manipulating pixels makes our technique fully independent of the actual 2D or 3D objects that constitute the representation. However, this approach also has some limitations. One limitation is that performance depends on the magnification factor and size of the lens, as a consequence of the increased level of detail in the focus. Another issue is related to the quality of the rendering in the transition area for lenses that make use of distortion: as points get compressed in the transition region, small objects such as points may be lost, and lines cut if they fall between pixels, especially for high magnification factors. This problem can be partially addressed by specifying an expression of G comp that matches G scale , but this, in turn, can introduce unwanted rendering artefacts. Solutions based on MIP maps [START_REF] Williams | Pyramidal parametrics[END_REF] can help address this issue, but will be computationally expensive if the content of the representation in the magnified region varies continuously.

SUMMARY

We have presented an approach to the implementation of constrained magnification lenses for navigation in large workspaces, based on the displacement and compositing of pixels from two renderings at different scales. This technique has several practical advantages such as its independence with respect to the type of representation and its low cost of implementation. But more importantly, it allows for a variety of dynamic transitions between the focus and context regions, including -but not limited to -those covered in the Sigma Lens framework. This framework enables the design of new lenses, such as the SPEED-COUPLED BLENDING lens, which has been shown to perform very efficiently through a series of controlled experiments that cover cognitive aspects of navigation tasks ranging from motor performance to legibility issues on various types of representations.

Fig. 1 .

 1 Fig. 1. Three different lenses obtained with minor modifications to the scale and compositing functions: (a) a distortion lens on a high-resolution bitmap (subway map), (b) a hovering lens on 2D vector graphics and text (ACM UIST keyword tag cloud), (c) a speed-coupled blending lens on a 3D model of the Moon orbiting the Earth

FocusFig. 2 .

 2 Fig. 2. Gaussian distortion lens. The level of detail in the flat-top is increased by a factor of M M = 4.0

Fig. 3 .

 3 Fig. 3. Simple distortion lens

Fig. 4 .

 4 Fig. 4. Blending lens

Fig. 5 .

 5 Fig.5. Smoothing lens edges, on a magnified view of the Antarctic peninsula[START_REF] Stockli | The Blue Marble Next Generation -A true color earth dataset including seasonal dynamics from MODIS[END_REF]

Fig. 8 .

 8 Fig. 8. Targets' order of appearance in a trial (targets are twice their actual relative size for legibility purposes).

1 SCBFig. 10 .

 110 Fig. 10. Mean completion time per T echnique × M M condition.

2 Fig. 11 .

 211 Fig. 11. Mean completion time per M M × T echnique condition.

Fig. 12 .

 12 Fig. 12. (a) Exp. 4 graph (labels displayed in black) and (b) Exp. 4 map (labels displayed in yellow over a black background). Viewports are cropped to show details.

Exp. 4

 4 graph Exp. 4map Lens F1,11 = 54, p < .0001 F1,11 = 150, p < .0001 M M F1,11 = 32, p < .0001 F1,11 = 48, p < .0001 Lens×M M F1,11 = 20, p < .0001 F1,11 = 29, p < .0001

Fig. 14 .

 14 Fig. 14. Exp. 4 graph and 4 map : T ime and Acquisition errors.

/

  /focus color data access with texture2D(lensTex,vec2(x * 1.0/texWidth,y * 1.0/texHeight)); //context color data access with texture2D(lensTex,gl_TexCoord[texNum].st);

TABLE 1

 1 Summary of design for Experiment 3 Experiment 4 graph and 8 series of 4 trials in Experiment 4 map .

Emmanuel Pietriga received a PhD degree in computer science from Institut National Polytechnique de Grenoble (France) in 2002. He worked for INRIA and Xerox Research Centre Europe, did his postdoctoral research at MIT (Boston, MA) as a team member of the World Wide Web Consortium, and is now back at INRIA as a research scientist. He works on interaction techniques and tools for interactive structured graphics environments such as multi-scale user interfaces.

Olivier Bau received a M.S. degree in computer science from Universit é Joseph Fournier (Grenoble, France) in 2006. He is currently a PhD candidate in the Department of Computer Science at Universit é Paris-Sud (France). His research interests include human-computer interaction, computer graphics and design.

Caroline Appert received a PhD degree in computer science from Universit é Paris-Sud (France) in 2007 and did her postdoctoral research at IBM Almaden (CA, USA). She is now a permanent research scientist at CNRS (France). Her past and current work focuses on the design of tools for programming and evaluating advanced interaction techniques.