Rorik Henrikson

Bruno De Araujo

Fanny Chevalier
email: fanny.chevalier@inria.fr

Karan Singh

Ravin Balakrishnan

Multi-Device Storyboards for Cinematic Narratives in VR

Keywords: Virtual Reality, storyboard, sketching, 3D, movie. ACM Classification H5.2 [User interfaces]: Graphical user interfaces, Virtual Reality, H5.m [Miscellaneous]: Stereoscopic display

INTRODUCTION

Head-mounted displays (HMDs) have evolved over half a century from research prototypes [START_REF] Sutherland | A head-mounted three dimensional display[END_REF] to consumer products [START_REF]Google Cardboard[END_REF][START_REF] Htc Vive | [END_REF]38]. The entry of VR technology into homes has caused a surge of interest in the medium among developers, filmmakers and storytellers. Major film festivals, studios, and technology companies [START_REF] Frost | 360-degree VR Video invades Disney's theme parks[END_REF][START_REF] Mcnally | Warner Brothers Announces Plans for a Virtual Reality Batman: The Animated Series Project[END_REF][START_REF] Trenholm | Samsung to open VR movie studio in New York: 'We love stories[END_REF][START_REF]Oculus Story Studio[END_REF] have created teams specifically targeted at VR stories: where live-action, or animated narratives occur in fully immersive environments, where the viewer experience is uniquely intimate.

VR is characterized by a quality known as presence -the feeling of actually being on location in a story rather than experiencing it from the outside [START_REF] Slater | Depth of Presence in Virtual Environments[END_REF]. This new medium provides a unique opportunity for viewer engagement and the exploration of novel storytelling, but requires the development of new cinematic constructs and film language [START_REF] Pausch | Disney's Aladdin: first steps toward storytelling in virtual reality[END_REF].

Creating a movie for VR is not as simple as taking a regular script and going through the well-developed film making process. The unique properties of VR require directors to consider concepts such as presence and peripheral vision, and use them effectively. Directors also must address the challenge of guiding an audience through a narrative, while leaving them free in a fully immersive environment, to look or move in any direction, and even trigger events within the environment. Traditional cinematic principles of cuing and staging can help solve this problem, but need to evolve with the immersive use of spatial visual and auditory cues.

We learned through our multiple interviews that, no one currently knows how to properly plan for immersive narratives. Traditional storyboards and planning tools are shallow and restrictive given the full extent of the environment that needs to be discussed. Communicating ideas between individuals is further impeded by the experiential quality of VR. Film teams thus rapidly model, collect, and assemble assets that are viewable in VR, simply to form the basis for team discussions, so everyone can understand and plan for the unique challenges being faced by the project.

To help address this unique set of problems, we sought to explore a workflow specific to the needs of professionals creating storyboards for VR and the related challenges; to enable teams to conduct initial explorations and collaborate at/near the speed currently possible with traditional film.

To facilitate this goal, we conducted a series of semistructured interviews with a variety of film professionals to fathom the design and technical challenges. The interviews gave insight on how experts regard the space of VR narratives relative to traditional filmmaking, and the processes and tools to plan for immersive experiences, in use today.

We used this information to design a two-device interactive storyboard system for tablet and VR, that leverages both the speed and skills of a storyboard artist, and allows a director to experience the results in VR simultaneously.

We address a number of issues in a working prototype of our collaborative multi-device storyboard design: ensuring homogeneity between the different viewing environments; supporting quick authoring, fast navigation, and a proper overview of the fully charted story. This prototype was presented to VR film professionals and feedback was elicited on different aspects of the design, its ability to address the needs of planning narratives in VR, and to assess if the proposed workflow was worthy of further exploration.

Our contribution is thus a principled survey of the state of the art in cinematic VR planning, and the first multi-device system that supports a storyboard workflow for VR film.

FORMATIVE STUDY

To properly understand the differences between traditional and VR film creation and current planning processes, we talked to a variety of professionals, who each had at least 10 years of experience working with film, television, and VR. We distill here the result of semi-structured interviews with three producers, four directors, one executive creative director, one technical director and one storyboard artist.

Stories in Virtual Reality

Unlike movies that are projected on a silver screen, VR films can intimately engage audiences. These films are often referred to as stories in the industry, reflecting a looser terminology used by professionals. We will henceforth refer to these VR stories as VRSs. Also, as with our interviewees, we refer to "story" or "narrative" as the content being told, while the "VR experience" is what the audience consumes.

Relationship of Story and Audience

At a high level, we formulate a film experience using three components: the audience, the camera, and the narrative (or story). The narrative is a collection of moments presented in some predetermined order. These moments may be temporally sequential, or non-linear, and they may be told within a continuous environment, or jump from one loca-tion to another. The audience is a group of one or more individuals who experience the story being told. The camera is a mechanism to control this experience: framing shots, camera movement, stereoscopy, and field-of-view (FOV) are all variables in aligning the audience with the narrative.

With traditional film, the director is usually in complete control of the narrative and camera, with the audience generally experiencing the story from outside the movie's environment. In VR, this arrangement is not as clear. With a VRS, the narrative remains in the director's control, but the audience is part of the story; the narrative occurring all around them. The notion of a camera, is also less definite. The camera is loosely the viewer's FOV (typically frameless) that the audience controls, though a director controls intrinsic camera parameters e.g. stereoscopy and lens filters (color, shading, graininess), and can subtly or explicitly guide or control audience gaze throughout the narrative.

Directors are actively experimenting with various configurations of our audience-camera-narrative model in VR: virtual movie theatres; immersive environments where the viewer can look anywhere, but the narrative is focused in one primary place; environments where multiple narratives happen simultaneously in different places; a primary "stage" that slows down and eventually stops as the viewer looks away [START_REF]Visionary VR[END_REF]; camera concepts where audiences attach themselves at any time to any character to follow that character's story arc [START_REF] Bishop | Inside Industrial Light & Magic's secret Star Wars VR lab[END_REF]; and the ability to teleport anywhere, to follow a story as much or as little as desired. These techniques allow for different levels of interaction. We propose that a narrative shifts from a VRS to a game when a viewer's interactions change the outcome of the story (e.g. a character dies as a result of a viewer's choice). In this paper, we focus on VRSs, where the viewer control is limited to their consumption of the story, not its outcome.

Making VR Stories: Key Considerations

Though many of the concepts and approaches used for creating a VR experience are similar to conventional cinema, others are more akin to live theatre and plays. This interplay results in many new concepts that one must consider that are unique to authoring these experiences.

Presence -One of the biggest differences from traditional film is a concept that is referred to as presence [START_REF] Slater | Depth of Presence in Virtual Environments[END_REF]. Presence is the feeling of being inside a scene rather than looking at one from the outside. For instance, looking at a family vacation photo may cause you to remember your experience of being there, but is unlikely to invoke a similar feeling in an outside observer. VRSs evoke a sense of being there, that is not captured by 2D/stereoscopic imagery.

Active experience -Movies have generally been passive, static experiences for the audience, allowing one to sit down and be taken on a journey as the story is told. VR experiences allow audience participation, where viewers can actively look and potentially move around to explore the immersive setting, while following a narrative.

No framing -With traditional film, the view is defined by a border within which a director can layout or frame a shot. As a result, with traditional film, a significant amount of attention and effort is used to plan and design a shot. VR typically has no border and no guarantee where a user will look. Framing is thus harder, even conceptually, which changes how a director approaches the planning of a shot.

Blocking -With VR, the space all around the audience can be used to stage a film. For this reason, the concept of blocking, the process of deciding what will be where, where objects and people will move, and the composition of a scene as a whole within the set changes. "How much of the film will happen in front of the user?", "What will happen behind the user?", and "How should one guide the viewer's attention from one area to another?" are just some of the considerations needed while planning the blocking for VR.

Peripheral vision -Since VR creates the sense of actually being on location, the director needs to think about the viewers' lines of sight. In the past, things that would have been off-camera can now be seen peripherally.

Audience attention -Keeping the audience focused on the narrative is an added directorial burden in VR. Sound, staging cues, lighting and movement can all be used to draw the user's attention; however, as an interviewee noted, these actions must be used sparingly, as audiences quickly desensitized and will ignore these techniques if used too often.

Limited Transitions -With traditional movies, directors rely on cuts, fade in/out, wipes and other shot transitions to keep the story engaging and to move the narrative from one moment to the next. In VR, transitions are more jarring and potentially disorienting, as they involuntarily "teleport" the audience. Interviewees indicated that VR directors have generally found that limited use of fades are the best way to transition between scenes. Due to this effect, many stories are told in one environment, effectively eliminating the need for transitions. Live theater has a similar constraint, not due to disorientation, but the inability to quickly or easily change physical sets or move the audience around.

Screen Format -A director has a wide choice of spatial staging formats in VR, from a virtual screen to a completely immersive environment.

Stitching -Current fully immersive VR video capture rigs mount multiple cameras omni-directionally, to immersively capture a live scene. Stitching these multiple camera images together often creates faint distortions and discontinuities along the seams. While future imagery may be seamless, current directors need to plan their shots to minimize viewer focus in the vicinity of seams.

Optics -A director's choice to present their movie monoor stereoscopically has a different dimension in VR. Stereoscopy is the effect created from each eye being shown a different image; one horizontally offset from the other, creating an illusion of depth through stereopsis. Leaving the picture monoscopic, a director relies on depth cues like retinal size, overlap, and aerial perspective [START_REF] Lipton | Foundations of the Stereoscopic Cinema: A Study in Depth[END_REF].

Duration -For the near future, VR films will be fairly short in length, both due to the complexity of authoring content and viewer fatigue from sustained viewing in VR.

Planning for VR Stories

Due to the multitude of decisions and technical challenges creating engaging experiences, directors need to plan a VRS in VR itself. This ensures that everyone works towards the same vision of the film and allows the film crew to organize a scene's logistics. For instance, lighting technicians can figure out light types and placement, stunt coordinators can discuss choreography and rig setup, and problems can be anticipated before anyone is on set, preventing costly mistakes. The various unique considerations for VR, however, render traditional planning tools such as storyboards and previsualization (Figure 2), ineffective in VR.

Storyboards

Storyboards, traditionally, are hand drawn sketches similar to comic strips that outline the key moments of a shot for a scene in a film [START_REF] Hart | The Art of the Storyboard: A Filmmaker's Introduction[END_REF]. Typically, they are small, quickly drawn rough sketches made to capture the essence of a moment in the story without the need for any underlying infrastructure. They allow a director to step through a movie to discuss concepts and moments, their relationship in the narrative, and to plan a compelling story. These boards are generally created very quickly by one or two artists. Storyboards are often distributed on set to aid organization.

Though great for discussing shots, traditional storyboards have disadvantages with VR. First, one cannot convey presence with a small 2D sketch. Also, since VR is mostly frameless, framing can distract from understanding. Lines of sight on a 2D picture have an abrupt border, where our visual acuity gradually fades at the periphery in VR. VR planning further entails blocking a 3D environment around the audience, instead of a limited field-of-view 2D plane.

Previs

Previsualization, or previs, is the technique of creating (usually) a 3D computer model of a film set, populated with virtual cameras and characters to explore and refine narrative breakdown and plan shots (Figure 2). While directors can freely explore camera angles and transitions, previs is expensive, time-consuming, and requires the creation of many digital assets early in the filmmaking process. Conceptually, previs can be used in other film contexts [START_REF] Zwerman | The VES Handbook of Visual Effects: Industry Standard VFX Practices and Procedures[END_REF]. Image from Wee Biz Studios.

Drawing and Painting in VR

There are some very compelling 3D tools for drawing and painting directly in VR, like TiltBrush [START_REF] Tiltbrush | [END_REF], where users paint in the air using 3D controllers, and Hyve3D [START_REF] Dorta | Hyve-3D: a new embodied interface for immersive collaborative 3D sketching[END_REF], where drawing on a spatially tracked tablet is mapped to virtual planes in a cave-like environment. Storyboards for early planning and blocking, however, should leverage existing skills of storyboard artist and support quick sketches of appropriate roughness, that provide a good spatial proxy for scene elements at the right level of abstraction.

Neither of the approaches are well suited to storyboards: inair interfaces like TiltBrush are too slow for prolonged use when creating many storyboard panels, and have no natural abstraction for blocking. A planar sketching interface like Hyve3D provides such an abstraction, but controlling arbitrary planes in space can be overkill and thus cumbersome.

Further, while stacked planar sketching is ideal for traditional and stereo storyboards [START_REF] Henrikson | Storeoboard: Sketching Stereoscopic Storyboards[END_REF], a more natural spatial extension to VR would be drawing on concentric cylinders or spheres around the audience.

Current VR Planning Strategies

We learned from professionals that there are currently no standards for planning VR projects, as there is no sufficient process for discussing evolving VR cinematic concepts. Consequently, groups cobble together 3D visual mockups (using images, projected 2D storyboard panels, 3D objects, toys, cardboard cut-outs, previs and other proxies), so presence in VR can be experienced and discussed.

For example, one group we interviewed uses a workflow that combines Mettle (an Adobe After Effects plugin for 360/VR) and Adobe Photoshop. Each asset is sketched in Photoshop and imported and manipulated onto planes in After Effects. The overall scene mock-up is exported to be later viewed using a Samsung Gear VR headset. Any iterations require the entire process to be painfully repeated, which obviously affects productivity. We thus set out to provide a solution of the same quality and efficiency as traditional storyboards, that leverage domain expertise (mimics pen and paper), is easy to edit by an artist or director, and provides real-time feedback in VR, which are all design requirements critical to effective storyboarding [START_REF] Henrikson | Storeoboard: Sketching Stereoscopic Storyboards[END_REF].

TOWARD A SYSTEM FOR VR STORY PLANNING

There are a number of questions and issues that need to be addressed in the design of a VR storyboard system:

How does one allow for the speed and familiarity of drawing on a tablet/paper in an immersive environment? What should a VR storyboard look like? How does one abstract an immersive environment that surrounds the audience into canvases for sketching? How does one collaborate and communicate in a virtual space, when visually separated from other discussants? How do we ensure storyboard sketches provide sufficient volume to perceive depth and spatial relationships between objects in a scene?

We started by asking our interviewees if a VR storyboard would be useful. The executive creative director commented "to [him], storyboarding in VR is the first step of tackling a big problem when creating content for the medium, and that is, all parties involved have something different in their imagination. Similar to a film, storyboarding in VR serves the purposes of getting everyone on the same page, gathering around the creative vision. Having a VR storyboard [would allow] for all parties involved to understand how their roles play into the larger picture." It was also stated that "Using a traditional storyboarding method would require exponentially more drawings/work/time, and even then there would be no sense of space or scale."

We propose a planning tool based on a networked multidevice system, where one can simultaneously exploit the sketching abilities of a tablet, and immersive viewing by wearing an HMD (Figure 1). Through a "best of both worlds" approach, an artist can draw on a tablet, working with panoramic sketch planes, and themselves, or collaboratively with a director, view the results instantly mirrored in VR to experience the scene from within.

We illustrate different possible workflows enabled by our multi-device approach in Figure 3. If the director (in a dark shirt) and artist (in a white shirt) are working synchronously in the same location (Figure 3-a, b), they could both sit around the tablet and have a discussion similarly to what is done for traditional film, or both view it in VR. Alternately, the director can immerse themselves in VR, while the artist sketches on the tablet live. In an asynchronous scenario, the artist could start by sketching and viewing on a tablet as is typical, or drawing on the tablet and viewing in VR. The director, working asynchronously, could at any time view the immersive VRS panels with the HMD and with the tablet add comments and notes for the artist to subsequently address (Figure 3-c, d).

While the physical tablet is not visible in VR, with the tactile feedback of the physical tablet, and the instant visual feedback of the sketch lines and stylus in VR, sketching is not a problem for digital artists used to drawing on digitizing tablets that are physically separate from the display.

To enable storyboard artists to sketch in a fast and familiar method on a canvas surrounding the viewer, and capture the well-understood cinematic concept of scene depth [START_REF] Henrikson | Storeoboard: Sketching Stereoscopic Storyboards[END_REF], we divide the space into a set of concentric cylinders around the viewer. Artists draw on unrolled cylinders shown as flat panoramic panels -a surface that is easier for artists to mentally unroll than a wrapped sphere. These panels can be rolled back into cylinders for immersive displays (Figure 5). While this depiction is best suited to a 360° view, it is nonetheless able to quickly depict 3D scenes that can be arbitrarily navigated and viewed for VR cinematic discussions.

WORKING PROTOTYPE

We present a solution to enable initial assessments of our proposed workflow. Our implementation combines a tabletbased sketching tool (Microsoft Surface Pro 2.0) to author VR storyboards, and a synchronized HMD (Oculus Rift DK2) to experience the boards immersively.

Many design innovations of our dual system were based on supporting synchronous use of the tablet for sketching, and the HMD for experiencing the VRS panels from within.

Given the lack of ability to currently storyboard for VR, rather than trying to establish specific input techniques, the goal of this first prototype was to explore and assess a workflow that enables teams to conduct early explorations, collaborate at/near the speeds currently possible for traditional film with a VR system, and to see whether storyboards are even useful at this early stage for VR.

We first describe the authoring of a storyboard on the tablet. Then we describe how the artist or the director experiences the result in VR, and can annotate using the tablet. Finally, we discuss how our dual system supports collaborations between the artist and director (Figure 3).

Authoring VR stories on the tablet

The primary storyboarding activity consists of sketching, and viewing a series of moments (panels) that make up a narrative. The tablet presents a manifestation of the unrolled concentric cylinders, enabling the artist to sketch on the 360° environment of the VRS panels.

Sketching View

Like traditional storyboard tools, our system includes a sketch canvas, where the artist can draw content for a panel. As in Storeoboard [START_REF] Henrikson | Storeoboard: Sketching Stereoscopic Storyboards[END_REF], she can add strokes at different view depths (i.e., concentric cylinders), by navigating a slider bar, to support the director's spatial vision. The bar is augmented with thumbnails to show the placement of the strokes that are present in the environment (Figure 4).

To maximize the drawing area, rather than presenting the entire panel unwrapped, the tablet shows a smaller portion of the current panel. Swiping left or right, the artist can access the rest of the drawing space. The canvas smoothly wraps around as the artist reaches the edge of the panorama.

As the artist develops the narrative, she can add new panels to describe new moments in the story. Tapping on the edge of the canvas, the artist can easily access the previous (left) or the next (right) panel of the VRS.

Technically, one of the main challenges of drawing on a cylindrical panorama is to provide a drawing surface that accounts for the canvas' curvature when projecting on the drawing surface. We discard such correction, i.e. we provide a flat canvas, since in practice, artists draw at sufficient viewing depths that the distortion becomes negligible.

Overhead View

An important aspect of storyboarding in VR is to visualize overall layout of the immersive scene. Drawing inspiration from a technique currently used by VR directors, we aid the quick placement and blocking of objects via an overhead view (Figure 6), which allows the artist (and the entire film crew), to see all sketch strokes for a VRS panel, in a target view (right) with a preview window (left). The overhead target is divided into 30° segments with concentric circles to highlight given depths. Colored segments drawn over the circle convey the radial locations of scene content, allowing the artist to identify crowded and empty spaces, as well as distances between sketch elements in the virtual environment. The current view direction (seen in elevation in the top-left preview window) is represented by a gray wedge, similar to radar, and can be manipulated by rotating the wedge around, to update the preview window.

Flipping back and forth between panels in this view allows the artist (and director) to see how audience attention is being guided over the course of the narrative, understand the flow of action, as well as spot abrupt changes in depth and location, which can be disorienting for the audience.

Simple interactions allow the artist to quickly edit the spatial composition of the panel. She can adjust depth and location of strokes by lasso selecting with the pen (in either the overhead target or the preview window) and dragging the selected lines with a finger. We thus leverage pen and touch interaction for different activities, supporting artistic workflow with minimal interruption [START_REF] Hinckley | Pen + touch = new tools[END_REF].

Panoramic Storyboard View

As in traditional storyboards, we provide an overview of the VRS, showing the sequence of panels as panoramic thumbnails, under which the artist can add notes (Figure 7). From this view, the artist can also quickly jump between panels for further edits in the sketching view.

To heed the VRS planning of audience attention, a concern unique to VR storyboards, we highlight the primary area of focus for each panel (green box and gradient in Figure 7). Panoramas are aligned with respect to the view angle (see angular scale under thumbnails), allowing the artist to understand and experiment with different focus transitions along subsequent panels, and maximize the use of the stage.

With its sketching, overhead, and panoramic storyboard views, the tablet provides the artist with a rich set of perspectives of the VRS, supporting expressive authoring and providing assets for discussion between the director and crew. Transitions between the views is achieved through a simple pinch gesture, without disrupting the creative flow.

Exploring the virtual environment with the HMD

At any time during the process, the director, the artist, or any other collaborator can decide to experience how the VRS looks within the virtual environment, using the HMD. Design decisions for VR were largely based around a philosophy that the tablet draws, and the HMD views content.

HMD as an External Observer

An external observer (the director, or any other collaborator) can experience the panels as the audience would, and view sketched content wrapped around the cylinder in 3D, while the artist continues to work on the tablet (Figure 3-b).

To facilitate discussions around content, all changes that the artist makes on the tablet are immediately reflected in the VR environment. Meanwhile, the observer can look around at will without affecting the artist's environment, and may even decide to experience the scene from a slightly different viewing angle, through navigation with the keyboard. Similarly, the artist can freely work in any of the views (sketching, overhead, panoramic) without affecting the VR environment. Only when the artist changes the panel on the tablet, will the observer be teleported into the new scene.

HMD as a Display of the Tablet

A single user can immerse themselves in the VRS, while using the tablet, e.g. the artist can look at their creation in the HMD, and keep editing the content on the tablet (Figure 3-c, left); later, the director can look at the VRS immersively and make annotations on the tablet (Figure d,right).

While wearing the VR headset, the surrounding physical environment is invisible to the immersed user. Thus, the tablet and keyboard are less accessible. We rely on "within arm's reach" proprioception [START_REF] Mine | Moving objects in space: exploiting proprioception in virtual-environment interaction[END_REF] and haptic cues for interactions. In practice, drawing on the tablet is not hindered, as the canvas and pen are represented by a frame widget and cursor in VR (Figure 9), which is similar to artists working with 2D digitizing tablets. In this setup, we reduce the tablet interface to pen interaction for sketching, and touch to control the view, negating the need to remove the HMD. Finger dragging up and down changes the current working depth on the sketch surface, while panning rotates the view, i.e. the VR environment is rotated to the position shown on the tablet; but the user can still look left and right. While large rotations performed via the tablet can cause vestibular discomfort [START_REF] Akiduki | Visual-vestibular conflict induced by virtual reality in humans[END_REF], it is preferable to using the HMD gaze to control the tablet view. As the tablet is used for sketching, it should be insensitive to ambient HMD head movements. Still, free navigation using the keyboard remains available, and hotkeys allow easy access to tools and the undo action.

Diorama Storyboard View

Our interviews indicated that professionals were unsure what a storyboard for VR would look like. To initiate the discussion on this topic, we introduced a diorama storyboard (Figure 8) that acts as the VR counterpart of the panoramic storyboard view on the tablet. Panels are represented as a series of 3D miniatures within cylindrical discs with white backgrounds that contrast the strokes. Viewed from a 3 rd person perspective, these dioramas surround the user, rather than being organized traditionally in a flat grid. The panels can be viewed from different angles and proximities with keyboard navigation. Like the panoramic board, the user can jump between panels by looking at the desired diorama and with a key switch to sketching for that panel.

Support for Collaboration

Collaboration is an important design requirement of our dual system, as artists and directors often work together on storyboards, and may discuss them with other film crew. To enable the workflows illustrated in Figure 3, we synchronize the VRS panels via a wireless LAN using UDP messages, supporting consistency between devices, increasing awareness between users, and facilitating discussions.

Consistency Across Devices

To establish common landmarks for all users, we ensure consistency between the flat tablet's view and that of the HMD. First, the tablet and VR system display the same FOV (~90°), which occupies only half the screen given the same aspect ratio (freeing the other half for other purposes). Further, to help the director and artist mutually understand the VRS space, both interfaces contain a ground plane represented by a radial grid, and a degree scale wrapped around the environment for orientation (Figure 4 and9).

Though both devices show grid lines with the same perceptual spacing, they are not exactly the same. The HMD shows the 3D scene in accurate linear perspective. The tablet on the other hand presents the sketch cylinders unrolled into rectangles, ideal for sketching. Therefore, the ground plane projects as straight lines rather than radial lines on the tablet. We forego this accurate depiction for one that provides a better perception and interactive control. We draw the ground plane grid to perceptually match the grid in VR: with the concentric circular arcs as horizontal lines (that show the depth of the sketch cylinder), and the radial lines near vertical, but converging inward. Note that, two sliver regions outside the outermost radial lines are outside the VR field-of-view. We further show a dark horizontal line that moves along the ground plane to help the artist distinguish strokes above and below the ground plane (Figure 4).

Collaboration Feedback and Additional Features

Users in disparate visual spaces introduce a communication challenge, which we address using overlays indicating the current view, or gaze, of the other user on both devices.

While sketching on the tablet, the artist may notice a red horizontal bar along the bottom of the screen that moves to track the director's gaze in VR (Figure 4). With this mechanism, the artist can quickly pan the sketch surface to match that of the director during discussions. A similar VR fieldof-view indicator appears in the overhead view target on the tablet, as a pie wedge. Similarly, at the depth of the current sketch cylinder, an outline of the current view area of the tablet is shown in 3D on the HMD. This render overlay not only helps by showing what the tablet sees, but also defines the current 3D canvas for sketching while immersed.

Alternately, the tablet's view can be temporarily coupled to that of the HMD, sparing the artist the need to actively track where the director is looking, when the latter momentarily leads the discussion. The reverse is not advised, as an external controlling source may cause nausea on the HMD.

Finally, we support director's notes as a dedicated canvas (Figure 4) that we display in purple, distinct from content on the tablet and in VR (which can be toggled as needed).

Ultimately, we support the production of VRSs by artists following traditional storyboard language, and enables VR explorations which were not possible before. Integrated in a cohesive dual system, these enable new collaborative workflows between the artist, the director and overall film crew.

USER FEEDBACK

We conducted interviews with professionals from the VR cinematic industry to determine whether our dual system approach was worth pursuing. Our interviews focused on high-level feedback on the dual system to assess the workflow and its ability to support the creative process rather than focusing on particular UI components.

We solicited feedback from a producer and an executive creative director from an Emmy winning VR team (p1, p2), a director/producer from a leading VR company (p3), and a 3D Lumière award winning director of stereoscopic and VR films (p4). We invited these professionals to our lab to experiment with our system following a ten-minute demonstration of its functionality. They experimented with each context freely without any time constraint (i.e. using the tablet and HMD simultaneously, just the tablet then looking at the results in VR, etc.). We concluded the sessions with a semi-structured interview, where we elicited feedback on the system as a whole, as well as exploring specific points.

General Feedback

The general response we received regarding the system was all positive, eliciting comments like "I loved it… hugely valuable" (p1) and "from a prep side, it's a huge step forward" (p4). When asked about these responses, there was a consensus that the coupling of the devices and the ability to see the drawings simultaneously on the tablet and in VR was the biggest contributing factor to this feeling, "the simultaneous view in the [HMD] is amazing…a hit hands down" (p2).

Dual System Approach

We were interested in user response to the need for a tablet and a HMD. We found that the users were happy with this setup and viewed the flexibility this introduced as a benefit. One participant noted that the two-system approach allows artists to "intuitively block things in" and that when they put on the headset, "it's exciting to actually see [the scene]" (p2).

Participants also acknowledged that very few people can remain in a VR environment for a long period of time without feeling slightly ill. For a storyboard artist, to be immersed all day is impractical. It was felt that our system was a "good way to preview without using the [HMD]" (p1), and that it was actually positive that "[storyboard artists] don't have to be in [the VR environment] the whole time" (p2).

We inquired about possible problems caused by the disparity in the way viewers perceive the scene (i.e. panoramic panel on the tablet vs 3D interactive space in VR). None of the interviewees were concerned about this. It was felt that

"people will start to learn the relationship between what it looks like in panorama and what it looks like in a [HMD].

Having an experienced artist using your tool, you can get pretty far just in panorama view" (p1). Further, it was stated that "once [the storyboard artists] understands the concept they can just draw, [they] don't need to be in there." (p4)

Authoring

One goal with our system was to allow for quick storyboard creation despite the complexity of VR. Participants were able to quickly generate simple content during the interviews. Figure 9 shows some examples of their creations.

We inquired about what users liked about our system workflow and what could be improved. General comments were positive. Abilities such as "being able to toggle back and forth [between the panels] is awesome" (p1). It was felt, however, that there were a number of features we could add to improve on the existing system. The thumbnail slider bar was found to be a nuisance, and that it "got in the way" (p2).

The ground plane grid was found useful for a sense of spatial dimension, and similar scale feedback in the vertical dimension was suggested, as was a feature to toggle toscale silhouettes of an "apple, person and dinosaur" (p2).

General comments about the UI included suggestions that combine interactive control of the overhead and sketch surface view. It was also noted that with complex scenes, it is difficult to isolate items in the overhead view as they often overlapped. Therefore, a "function to explode out the lines that are overlapping" (p1) would be a useful addition.

VR Storyboards

When starting this project, we learned that, currently there are no such things as VR storyboards. Consequently, we created both the panoramic storyboard view and the diorama storyboard view. Users seemed to prefer the panorama storyboard view: "[I] can go scene one, scene two, scene three, and just see the subtle differences" (p2) and "you can see your primary point of focus" (p1).

Several of the professionals noted that though they did not have much use for the dioramas, they could see them being useful to other departments. "I could see [dioramas] being more useful in the future… if you end up moving cameras" (p2); "I think it would be useful for other departments" (p4).

Collaboration

The potential for a collaborative workflow with our system was recognized by users as a significant contribution. It was felt our system "allowed for creative collaboration where [the director and artist] were able to be in the same space and bounce things off of one another" (P4). One user stated that showing the location of the other user was "helpful 'big time'…when you're in the same space, it's pretty intuitive" (p1). However, it was also noted by this user that "if you were over the phone… [it would be useful] if there were some way for a person with the headset on to stare at something" (p1) to explicitly highlight object(s) of discussion.

Final thoughts

The users who tried our system were very excited about its potential. Being able to try shots without having to set-up cameras for test footage, and the ability to quickly and collaboratively create and discuss ideas, were all factors that contributed to their enthusiasm. One can often measure the success of an implementation by a user's willingness to use the system, and when we asked interviewees for final thoughts, we were told that, "if you had a [consumer] version ready tomorrow we'd use it" (p1).

RELATED WORK

Telling stories in a virtual environment is not a new concept. In early work, Randy Pausch et al. [START_REF] Pausch | Disney's Aladdin: first steps toward storytelling in virtual reality[END_REF] identified the need for a VR storytelling lexicon (that is currently evolving), and the need for rapid prototyping in VR. Our talks with current filmmakers suggest that this is still very much an open problem. Below we focus on existing tools that enable 3D sketching, and drawing in VR.

Sketching 3D models

Since Sutherland's seminal sketchpad system [START_REF] Sutherland | Sketchpad: a man-machine graphical communication system[END_REF] more than half a century ago, digital sketching of 3D objects has been an active area of research (see [START_REF] Olsen | Sketch-based modeling: A survey[END_REF] for a survey). A large body of research deals with interpreting a collection of 2D strokes as a network of 3D curves. Tools like Analytic 3D Drawing [START_REF] Schmidt | Analytic drawing of 3D scaffolds[END_REF], ILoveSketch [START_REF] Bae | ILoveSketch: as-natural-as-possible sketching system for creating 3d curve models[END_REF], and True2Form [START_REF] Xu | True2Form: 3D curve networks from 2D sketches via selective regularization[END_REF], define geometric relationships between curves in 3D based on inferences of 2D strokes, using regularity constrains. These curves are often treated as cleanly drawn 2D strokes projected onto 3D geometry (like our sketch cylinders). Other research, illustrated by the organic shape modeler Teddy [START_REF] Igarashi | Teddy: a sketching interface for 3D freeform design[END_REF], builds 3D objects by extruding or inflating sketch strokes.

As an ideation-stage sketching tool, 3D objects are both overkill and distract from the primary goal of story layout. Gesture based drawing systems provide rules to build 3D geometry [START_REF] Ding | PENCIL: a framework for expressing free-hand sketching in 3D[END_REF][START_REF] Forsberg | Seamless Interaction in Virtual Reality[END_REF][START_REF] Zeleznik | SKETCH: an interface for sketching 3D scenes[END_REF] or suggest plausible alternatives [START_REF] Igarashi | A suggestive interface for 3D drawing[END_REF].

Our work is better served by systems that mimic the fluidity of pen-and-paper [START_REF] Dorta | Hyve-3D: a new embodied interface for immersive collaborative 3D sketching[END_REF][START_REF] Tsandilas | Bri-coSketch: Mixing Paper and Computer Drawing Tools in Professional Illustration[END_REF], where no assumptions are made on the nature or semantics of sketched 2D strokes, save for projecting them onto concentric sketch cylinders that reflect view depth. Our abstraction of view depth is akin to 2.5D modeling [START_REF] Rivers | 2.5D cartoon models[END_REF], or techniques that conceptually subdivide space into volumetric layers [START_REF] De Paoli | SecondSkin: sketch-based construction of layered 3D models[END_REF].

Drawing in VR

Direct drawing in VR has been explored for over two decades [START_REF] Deering | HoloSketch: a virtual reality sketching/animation tool[END_REF], and has even been enhanced to provide techniques to paint in VR [START_REF] Keefe | CavePainting: a fully immersive 3D artistic medium and interactive experience[END_REF]. Numerous systems use a 2D plane as a mode of interaction for constructing in the 3D environment [START_REF] Angus | Embedding the 2D Interaction Metaphor in a Real 3D Virtual Environment[END_REF][START_REF] Ens | Ethereal planes: a design framework for 2D information space in 3D mixed reality environments[END_REF] whether it is a virtual 2D plane, or a physical drawing tablet represented in the 3D space [START_REF] Bowman | Designing Animal Habitats Within an Immersive VE[END_REF]. LaViola et al. [START_REF] Laviola | 3D spatial interaction: applications for art, design, and science[END_REF] provide a summary of different techniques for drawing in VR.

When worrying about speed and accuracy, research has shown that sketching 3D objects in a virtual space is less accurate and more time consuming than traditional sketch-ing [START_REF] Wiese | Investigating the learnability of immersive free-hand sketching[END_REF]. Given the large volume of sketches needed for storyboarding, we thus choose tablet-based sketching over direct drawing in VR.

LIMITATIONS AND FUTURE WORK

While the response to our prototype was very positive, there were many insightful suggestions that would improve future versions of the system, such as the following:

Our system does not address the concept of stitch lines, which vary by camera-rig. Directors often film test footage to check blocking of elements. Showing stitch lines on storyboards would greatly benefit planning and layout in VR.

Our system represents object using sketch strokes. Though effective and lightweight, this approach lacks explicit mass and volume, which can be useful for planning. Combining our sketches with previs quality 3D assets is interesting future work, along with a richer set of input options while in VR. Different input techniques: bi-manual input, sketch language, augmented real 3D sketching, and visualization all provide other promising areas for future exploration. Also, though this paper has focused on VR stories, we believe our dual system approach, and its planning features for 3D dynamic scenes would be useful in many other contexts such as gaming, education, architecture, and AR. Finally, our prototype was designed with two collaborators in mind. While many of our concepts scale from two people to a full team, it is yet to be deployed or tested in such a setting. In fact, a deployment study to observe the tool actively being used is a good next step to determine how to improve the workflow, and where to focus next.

CONCLUSION

With the consumerization of VR headsets, there is an explosion of interest in creating content for this medium. While filmmakers wish to tell stories in VR, tools to support this endeavor are next to none. We thus contribute the first system targeted at storyboarding in VR.

We performed a formative study to assess the challenges and goals of VR storytellers. We studied the tools available to them today, and the limitations. We then proposed a workflow that pairs a sketch tablet and VR display, and allows users to sketch on stacked panoramic panels, corresponding to concentric cylindrical surfaces of increasing view depth. This setup leverages the domain expertise of storyboard artists and enables interactions in VR between the director and artist. We implemented this approach and elicited early feedback from professional VR storytellers on our prototype. This system was received very positively, and responses indicated that our approach provided the speed and functionality needed for early stage planning, and the artifacts to properly discuss VR films.

Figure 1 :

 1 Figure 1: Our multi-device system supporting the planning of virtual reality stories: a storyboard artist sketches the virtual environment of a scene moment using a lightweight tablet-based interface, while the director experiences the scene within VR. Additional dynamic overhead (top-right) and panoramic views (bottom-right) offer different perspectives on the scene to further support planning.

Figure 2 :

 2 Figure 2: Previs (left) is used to plan for movie shots (right).Image from Wee Biz Studios.

Figure 3 :

 3 Figure 3: Examples of co-located / synchronous (a, b) and distant / asynchronous (c, d) workflows between the storyboard artist (in a white shirt) and the director (in a dark shirt) using our multi-device approach.

Figure 4 :

 4 Figure 4: The tablet sketching view, integrating director's notes and indicators.

Figure 5 :

 5 Figure 5: Concentric cylinders are unrolled into panoramic views for sketching.

Figure 6 :

 6 Figure 6: Overhead view of the sketch surface, showing preview window (left) and overhead target (right).

Figure 7 :

 7 Figure 7: Panoramic storyboard view showing the focus bounding box and focus gradient.

Figure 8 :

 8 Figure 8: Diorama storyboard view on the VR system.

Figure 9 .

 9 Figure 9. Examples of VRS panels created with our system, as seen in the HMD. Note, in the leftmost example, the gray frame widget that conveys the current view of the tablet.

Acknowledgments -We are grateful to the professionals who participated in our interviews and evaluation for their time and valuable feedback. We also thank our colleagues at the DGP lab for discussions throughout the project.


Rémy Boyer
email: remy.boyer@l2s.centralesupelec.fr

Frank Nielsen
email: nielsen@lix.polytechnique.fr

INFORMATION GEOMETRY METRIC FOR RANDOM SIGNAL DETECTION IN LARGE RANDOM SENSING SYSTEMS

Keywords: Optimal Bayesian detection, information geometry, minimal error probability, Chernoff/Bhattacharyya upper bound, large random sensing matrix

Assume that a N -dimensional noisy measurement vector is available via a N × R linear random sensing operation of a R-dimensional Gaussian signal of interest, denoted by s. The problem statement being addressed here is the study of the minimal Bayes' error probability for the detection of s where

When the exact derivation of this probability is intractable, statistical similarity metrics, nourishing their roots in the information geometry theory, are useful to characterize the exponential rate of the error probability. More precisely, the Chernoff information is asymptotically given by the minimum over s ∈ (0, 1) of the s-divergence. In many applications, it is hard to evaluate the s-divergence. Worse, due to the asymmetry of the s-divergence for the considered detection problem, the Bhattacharyya divergence (s = 1/2), cannot circumvent this problem. As a consequence, the derivation of the optimal value of s requires a costly numerical optimization strategy. In this work, we propose two contributions. The first one is to provide a closed-form expression of the asymptotic normalized s-divergence. The second contribution is to provide an analytic expression for the optimal value of s.

INTRODUCTION

Evaluate the performance limit for the "Gaussian information plus noise" detection problem is a challenging research topic, see for instance [START_REF] Baik | Eigenvalues of large sample covariance matrices of spiked population models[END_REF][START_REF] Loubaton | Almost sure localization of the eigenvalues in a gaussian information plus noise modelapplication to the spiked models[END_REF][START_REF] Bianchi | Performance of statistical tests for single-source detection using random matrix theory[END_REF][START_REF] Silverstein | Signal detection via spectral theory of large dimensional random matrices[END_REF][START_REF] Besson | Matched direction detectors and estimators for array processing with subspace steering vector uncertainties[END_REF][START_REF] Kay | Fundamentals of statistical signal processing: Detection theory[END_REF]. Given a binary hypothesis problem, the Bayes' decision rule is based on the principle of the largest posterior probability. Specifically, the Bayesian detector chooses the alternative hypothesis H1 if Pr(H1|yN ) > Pr(H0|yN ) for a given N -dimensional measurement vector yN and the null hypothesis H0, otherwise. Consequently, the optimal decision rule can often only be derived at the price of a costly numerical computation of the log posterior-odds ratio [START_REF] Kay | Fundamentals of statistical signal processing: Detection theory[END_REF] but an exact calculation of the minimal Bayes' error probability P (N ) e is often intractable [START_REF] Kay | Fundamentals of statistical signal processing: Detection theory[END_REF][START_REF] Diep | Arbitrarily tight upper and lower bounds on the Bayesian probability of error[END_REF]. To circumvent this problem, it is standard to exploit well-known information theory based bounds on P (N ) e [START_REF] Sinanović | Toward a theory of information processing[END_REF][START_REF] Kailath | The divergence and Bhattacharyya distance measures in signal selection[END_REF][START_REF] Cover | Elements of information theory[END_REF][START_REF] Ali | A general class of coefficients of divergence of one distribution from another[END_REF][START_REF] Hellman | Probability of error, equivocation, and the Chernoff bound[END_REF]. In particular, the Chernoff information [START_REF] Chernoff | A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations[END_REF][START_REF] Nielsen | Chernoff information of exponential families[END_REF] is asymptotically (in N ) relied to the exponential rate of P (N ) e . Due to its strong link to the powerful Amari's divergence in information geometry [START_REF] Nielsen | Chernoff information of exponential families[END_REF][START_REF] Amari | Methods of information geometry[END_REF][START_REF] Nielsen | Matrix information geometry[END_REF][START_REF] Yang | Riemannian median, geometry of covariance matrices and radar target detection[END_REF][START_REF] Formont | On the use of matrix information geometry for polarimetric sar image classification[END_REF], the Chernoff information turns out to be useful in many problems of practical importance as for instance, distributed sparse detection [START_REF] Chepuri | Sparse sensing for distributed detection[END_REF], sparse support recovery [START_REF] Tang | Performance analysis for sparse support recovery[END_REF], energy detection [START_REF] Lee | Generalized Chernoff information for mismatched Bayesian detection and its application to energy detection[END_REF], MIMO radar processing [START_REF] Sen | OFDM MIMO radar with mutualinformation waveform design for low-grazing angle tracking[END_REF][START_REF] Grossi | Space-time code design for MIMO detection based on Kullback-Leibler divergence[END_REF], network secrecy [START_REF] Boyer | Relative-entropy based beamforming for secret key transmission[END_REF], Angular Resolution Limit in array processing [START_REF] Tran | Angular Resolution Limit for array processing: Estimation and information theory approaches[END_REF], detection performance for informed communication systems [START_REF] Katz | Joint estimation and detection against independence[END_REF], etc. In addition, the Chernoff information can be tight for a maximal s-divergence over parameter s ∈ (0, 1). Generally, this step requires to solve numerically an optimization problem [START_REF] Nielsen | An information-geometric characterization of Chernoff information[END_REF] and often leads to a complicated and uninformative expression of the optimal value of s. To circumvent this difficulty, a simplified case of s = 1/2 is often used corresponding to the well-known Bhattacharyya divergence [START_REF] Sinanović | Toward a theory of information processing[END_REF] at the price of a less accurate estimation of P (N ) e . In this work, our primary goal is to derive a closed-form expression of the Chernoff information for any s ∈ (0, 1) for the detection of a R-dimensional Gaussian signal acquired via a N × R linear random sensing operation corrupted by an additional N -dimensional Gaussian noise for N → ∞ with N/R → β ∈ (1, ∞). A secondary contribution is to derive a simple approximated analytical expression for the optimal value of s. To reach this goal, it turns out that the large Random Matrix Theory (RMT) framework [START_REF] Tulino | Random Matrix Theory and Wireless Communications[END_REF][START_REF] Couillet | Random matrix methods for wireless communications[END_REF][START_REF] Marčenko | Distribution of eigenvalues for some sets of random matrices[END_REF][START_REF] Silverstein | On the empirical distribution of eigenvalues of a class of large dimensional random matrices[END_REF] will be relevant.

CHERNOFF INFORMATION FRAMEWORK

The Bayes' detection theory

Let Pr(Hi) be the a priori hypothesis probability with Pr(H0) + Pr(H1) = 1. Let Pr(yN |Hi) and Pr(Hi|yN ) be the i-th conditional hypothesis and the posterior probabilities, respectively. The Bayes' detection rule chooses the hypothesis Hi associated with the largest posterior probability Pr(Hi|yN ). Introduce the indicator hypothesis function according to φ(yN ) ∼ Bernou(α) where Bernou(α) stands for the Bernoulli distribution of success probability α = Pr(φ(yN ) = 1) = Pr(H1). Function φ(yN ) is defined on X → {0, 1} where X is the data-set enjoying the following decomposition X = X0 ∪ X1 where X0 = {yN : φ(yN ) = 0} = X \ X1 and

X1 = {yN : φ(yN ) = 1} = yN : Ω(yN ) = log Pr(H1|yN ) Pr(H0|yN ) > 0 = yN : Λ(yN ) = log Pr(yN |H1) Pr(yN |H0) > log τ
in which τ = 1-α α , Ω(yN ) is the log posterior-odds ratio and Λ(yN ) is the log-likelihood ratio. The average error probability is defined as

P (N ) e = E{Pr(Error|yN )} (1)
with

Pr(Error|yN ) = Pr(H0|yN ) if yN ∈ X1, Pr(H1|yN ) if yN ∈ X0.
The standard strategy to minimize Pr(Error|yN ) for a given yN is min {Pr(H0|yN ), Pr(H1|yN )} [START_REF] Kay | Fundamentals of statistical signal processing: Detection theory[END_REF]. So using eq. ( 1), the minimal average error probability can be expressed according to

P (N ) e = E min {Pr(H0|yN ), Pr(H1|yN )} = X min (1 -α)Pr(yN |H0), αPr(yN |H1) dyN (2)
using the Bayes' relation.

Chernoff Upper Bound (CUB)

Using min {a, b} ≤ a s b 1-s with a, b > 0 and s ∈ (0, 1) in eq. ( 2), the minimal error probability is upper bounded according to

P (N ) e ≤ α τ s X Pr(yN |H0) s Pr(yN |H1) 1-s dyN def. = α τ s • exp[-µN (s)] (3)
where

µN (s) = -log M Λ(y N |H 1 ) (-s) (4)
is the (Chernoff) s-divergence and MX (t) = E exp[t • X] is the moment generating function (mgf) of variable X. Term µN (s) characterizes the exponential rate of the error exponent of P

(N ) e

. The Chernoff information, denoted by µ(s), is an asymptotic characterization on the best achievable Bayes' error probability and is derived according to [START_REF] Sinanović | Toward a theory of information processing[END_REF][START_REF] Cover | Elements of information theory[END_REF][START_REF] Ali | A general class of coefficients of divergence of one distribution from another[END_REF][START_REF] Dembo | Large deviations techniques and applications[END_REF] :

-lim N →∞ log P (N ) e N = lim N →∞ µN (s) N def. = µ(s). (5)
As parameter s is free, the Chernoff information can be retrieved as the unique minimizer:

s = arg min s∈(0,1) µ(s). (6)
Finally using eq. ( 3), eq. ( 5) and eq. ( 6), we obtain the Chernoff Upper Bound (CUB). The Bhattacharyya Upper Bound (BUB) is obtained by eq. ( 3) and eq. ( 5) and by fixing s = 1/2 instead of solving eq. ( 6).

INFORMATION GEOMETRY FOR LARGE RANDOM SENSING MATRICES

Model definition and associated binary hypothesis test

Assume that we dispose of N noisy measurements collected in vector yN via a linear random sensing operation where the i.i.d. noise n ∼ N (0, σ 2 IN ) is assumed to be statistically independent of the i.i.d. signal of interest s ∼ N (0, σ 2 s IR) where N > R. The random sensing system is modeled thanks to the N × R matrix Φ whose each entry is an i.i.d. random variable generated as an observable/known single realization of an unspecified probability distribution function parametrized by a zero-mean and a variance of 1/R. Let SNR = σ 2 s /σ 2 be the signal to noise ratio. The detector chooses the null hypothesis H0 for a null SNR and chooses H1, otherwise. More formally, the considered binary hypothesis test is

H0 : yN ∼ N 0, Σ0 = σ 2 IN , H1 : yN ∼ N 0, Σ1 = σ 2 SNR • ΦΦ T + IN . (7)
The data-space for hypothesis H1 is given by

X1 = yN : y T N (Σ -1 0 -Σ -1 1 )yN > τ (8)
with τ = log detΣ 0 τ 2 detΣ 1 where det(•) stands for the determinant. The performance of the above detection problem is clearly related to the question: "How can the covariance matrices Σ0 and Σ1 be discriminated ? ". This is a canonical problem in the context of the theory of information geometry for covariance matrices.

Chernoff information for a large sensing matrix

In this section, we derive a closed-form expression the CUB for the test of eq. ( 7) in the regime

N → ∞ with N/R → β ∈ (1, ∞).
Lemma 3.1 The log-mgf given by eq. (4) for test of eq. ( 7) is given by

µN (s) = 1 -s 2 log det SNR • ΦΦ T + I - 1 2 log det SNR • (1 -s)ΦΦ T + I . ( 9
)
Proof See Appendix 6.1

Result 3.2 Using Lemma 3.1, the Chernoff information defined in eq. (5) takes the following simple expression:

µN (s) N a.s -→ µ(s) = (1 -s) 2β Ψ β (SNR) - 1 2β Ψ β SNR • (1 -s) (10)
with a.s standing for "almost sure convergence" and

Ψ β (x) = β log 1 + x - Φ 2 β (x) 4 + log 1 + βx - Φ 2 β (x) 4 - Φ 2 β (x) 4x , Φ β (x) = x(1 + β) 2 + 1 -x(1 -β) 2 + 1.
Proof See Appendix 6.2.

Using Result 3.2, the Bhattacharyya information is given by

µ 1 2 = Ψ β (SNR) 4β - 1 2β Ψ β SNR 2 . ( 11
)

Chernoff information in the high SNR regime

The derivation of an analytic expression for µ(s) allows to obtain for an insignificant computational cost the CUB. This is crucial for large sensing systems. Another advantage is that given an analytic expression for µ(s), it is possible to derive in closed-form s and thus to avoid the costly numerical optimization step of eq. ( 6). The following Results provide analytic expressions for s and for the Chernoff information in the high SNR regime.

Result 3.3 In the high SNR regime, the optimal parameter s is obtained analytically according to

s SNR 1 ≈ 1 - 1 Ψ β (SNR) . ( 12
)
Proof See Appendix 6.3.

Result 3.4 The Chernoff information takes the following simple expression:

µ(s ) SNR 1 ≈ 1 2β 1 -Ψ β SNR Ψ β (SNR) . ( 13
)
Proof The proof is straightforward using eq. ( 10) and eq. ( 12).

NUMERICAL ILLUSTRATIONS

In this simulation part, the sensing matrix Φ is generated as a prescribed single 60 × 10 Gaussian realization with E[Φ]n,r = 0 and E[Φ] 2 n,r = 1 R δn-r. We fix α = 1/2. On Fig. 1, the Chernoff information (using Result 3.2) and the normalized s-divergence with respect to parameter s are drawn. First, we can see that the numerical and closed-form expressions are almost merged. In addition, the Chernoff information is asymmetric. This means that s = 1/2 and thus the Bhattacharyya information cannot be considered as the best strategy. On Fig. 2, the closed-form expression of eq. ( 12) obtained in the high SNR regime is illustrated by comparison with the numerical optimization of eq. ( 6) involving eq. ( 9). We can note that the proposed analytical expression of eq. ( 12) accurately predicts the coefficient s for a wide range of SNR greater than approximatively 10 dB. We can also note that the BUB is interesting only in the very low SNR regime. To study the detection performance, the upper bound on P (N ) e has been drawn in linear (resp. log) scale on Fig. 3 (resp. Fig. 4) for a wide range of SNRs. On these figures, several configurations of CUB and BUB are compared and detailed in Table 1. We can check that the BUB2 given by eq. ( 11) as a closed-form expression is an efficient and low cost upper bound for negative SNRs. Fig. 3 and in particular Fig. 4 illustrate that the BUB is a relaxed upper bound in the high SNR regime. As expected, the CUB3 which is derived in the high SNR regime is not informative for negative SNRs. But, we can observe that the CUB3 given by eq. ( 13) provides a very accurate and low cost solution to upper bound the error probability P (N ) e for positive SNR.

CONCLUSION

In the Bayes' detection framework, the performance in term of the minimal error probability, P (N ) e , for the detection of a randomly acquired R-dimensional Gaussian signal corrupted by a Ndimensional Gaussian noise is a canonical problem in the framework of the geometry information of covariance matrices. Indeed, P In many applications, it is hard to obtain closed-form expressions of the s-divergence for any s ∈ (0, 1) and of the optimal parameter s in a realistic computational time. The default choice s = 1/2 corresponding to the Bhattacharyya information is shown to be not the optimal strategy since the s-divergence is asymmetric for the detection problem of interest. In this work, we propose two contributions. The first one is to provide a closed-form expression of the Chernoff information for linear random sensing systems. The derivation of such analytic expressions has two mains advantages. Firstly, the Chernoff information for any s ∈ (0, 1) and Bhattacharyya information can be evaluated thanks to an analytic expression and thus for a very low computational cost. Secondly, the Normalized log-mgf s Comput. cost CUB1 Numeric with eq. ( 9) Numeric Highest CUB2 Analytic with eq. ( 10) Numeric Medium CUB3 Analytic with eq. ( 13) Analytic Lowest BUB1 Numeric with eq. ( 9) 1/2 High BUB2 Analytic with eq. ( 11 1 optimal parameter s is derived analytically in the high SNR regime. The log-mgf in eq. ( 4) for the following binary hypothesis test H0 : yN ∼ N (0, Σ0) , H1 : yN ∼ N (0, Σ1) is given by [START_REF] Nielsen | Chernoff information of exponential families[END_REF]:

µN (s) = 1 2 log det(sΣ0 + (1 -s)Σ1) [detΣ0] s [detΣ1] 1-s . ( 14
)
Using the expressions of the covariance matrices Σ0 and Σ1, the numerator in eq. ( 14) is given by N log σ 2 + log det SNR • (1 -s)ΦΦ T + I and the two terms at its numerator are log[det Σ0] s = sN log σ 2 and

log[det Σ1] 1-s = (1-s) N log σ 2 +log det SNR • ΦΦ T + I .
Using the above expressions, µN (s) is given by eq. ( 9).

Proof of Result 3.2

For N, R → ∞ with N/R → β ∈ (1, ∞), eq. ( 10) is derived using Lemma 3.1 and the following property (see [START_REF] Tulino | Random Matrix Theory and Wireless Communications[END_REF][START_REF] Couillet | Random matrix methods for wireless communications[END_REF][START_REF] Marčenko | Distribution of eigenvalues for some sets of random matrices[END_REF][START_REF] Silverstein | On the empirical distribution of eigenvalues of a class of large dimensional random matrices[END_REF] for instance):

1 N log det x • ΦΦ T + I a.s -→ 1 β Ψ β (x) where function Ψ β (•) is defined in Result 3.2.

Proof of Result 3.3

The first step of the proof is based on the derivation of an alternative expression of µN (s) given by eq. ( 14) involving the inverse of the covariance matrices Σ0 and Σ1. Specifically, we have

µN (s) = 1 2 log (detΣ0)(detΣ1)det((1 -s)Σ -1 0 + sΣ -1 1 ) [detΣ0] s [detΣ1] 1-s = - 1 2 log det [(1 -s)Σ -1 0 + sΣ -1 1 ] -1 [detΣ0] 1-s [detΣ1] s . ( 15
)
The second step is to derive a closed-form expression in the high SNR regime using the following the approximation (see [START_REF] Behrens | Signal processing applications of oblique projection operators[END_REF] for instance):

x • ΦΦ T + I -1 x 1 ≈ Π ⊥ Φ = IN -ΦΦ †
where Π ⊥ Φ is an orthogonal projector such as Π ⊥ Φ Φ = 0 and Φ † = (Φ T Φ) -1 Φ T . The numerator in eq. ( 15) is given by

(1 -s)Σ -1 0 + sΣ -1 1 -1 SNR 1 ≈ σ 2 IN -sIN + sΠ ⊥ Φ -1 = σ 2 IN -sΦΦ † -1 .
As sΦΦ † is a rank-R projector matrix scaled by factor s > 0, its eigen-spectrum is given by s, . . . , s R , 0, . . . , 0 N -R . In addition, as the rank-N identity matrix and the scaled projector sΦΦ † can be diagonalized in the same orthonormal basis matrix, the n-th eigenvalue of the inverse of matrix IN -sΦΦ † is given by

λn IN -sΦΦ † -1 = 1 λn {IN } -sλn ΦΦ † = 1 1-s , 1 ≤ n ≤ R, 1, R + 1 ≤ n ≤ N
with s ∈ (0, 1). Using the above property, we obtain

log det [IN -sΦΦ † ] -1 = log N n=1 λn IN -sΦΦ † -1 = -R log(1 -s).
Finally, thanks to eq. ( 15), we have µN (s) N Finally, to obtain s in eq. ( 12), we solve ∂µ(s) ∂s = 0.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Chernoff information and normalized s-divergence vs s with SNR = 20 dB

1 .

 1 Proof of Lemma 3.1

  -s) + s 2N log det SNR • ΦΦ T + I a.s -→ µ(s) SNR 1 ≈ 1 2β log(1 -s) + s • Ψ β (SNR) .

Table 1 .

 1 Description of the tested configurations in Fig.3 and 4

	)	1/2	Lowest


Ehud Gudes
email: ehud@cs.bgu.ac.il

Reputation -from Social Perception to Internet Security

Reputation is a concept that we use in many aspects of our social life and as part of our decision making process. We use reputation in our interaction with people or companies we do not know and we use it when we buy merchandize or reserve a room in a hotel. However, reputation plays also an important role in the internet society and enables us to establish trust which is essential for interaction in the virtual world. Reputation has several important aspects such as Aggregation, Identity and Transitivity which make it applicable in completely different domains. In this presentation we show the use of these aspects in several different domains and demonstrate it with our own previous and current research on reputation.

A good name is more desirable than great riches; to be esteemed is better than silver or gold.

Introduction

Reputation is a key concept in our social life. Many of our day to day decisions such as which book to buy or which physician to consult with are based on Trust. This trust is based either on our own direct experience or when such direct experience is lacking, on other people (whose opinion we value) direct experience. However when no such direct or indirect experience is available we tend to rely on an aggregated opinion of a large set of people or a community which is manifested as Reputation. Reputation plays also a major role in virtual communities and social networks. Attempts to tarnish reputation in social networks have caused much damage to people in recent years (several cases of suicide have been reported as a result of tarnished reputation). So maintaining a good online reputation becomes a critical issue for both people and businesses. The existence of easily accessible virtual communities makes it both possible and legitimate to communicate with total strangers. Such interaction however must be based on trust which is usually based on personal experience. When such experience is not readily available, one often relies on reputation. Thus, computing reputation to capture a community's viewpoint is an important challenge.

Reputation has become a key component of several commercial systems such as E-bay [START_REF] Dellarocas | Analyzing the economic efficiency of ebay-like online reputation reporting mechanisms[END_REF]. Also, quite a few models for trust and reputation were developed.

Different models use different conceptual frameworks including simple average of ratings, bayesian systems, belief models [START_REF] Jøsang | The beta reputation system[END_REF] which enable the representation of uncertainty in rating, flow models in which the concept of transitive trust is central such as Eigen-trust [START_REF] Kamvar | The eigentrust algorithm for reputation management in p2p networks[END_REF] and Page-rank [START_REF] Parreira | Efficient and decentralized pagerank approximation in a peer-to-peer web search network[END_REF] and group-based models such as the Knot model [START_REF] Gal-Oz | A robust and knot-aware trust-based reputation model[END_REF]. In this presentation we discuss three important aspects of reputation and show how they are used in different domains. While the first two domains we discuss involve reputation of real-life users, the third domain deals with abstract entities, internet domains, yet computing and using reputation in this domain is similar to its use in the social domain.

The first aspect we deal with is the use of reputation as part of an Identity. In the social domains, reputation is an important part of a person identity, and the identity of a person determines its permitted actions. An expert programmer may gain more access rights to an open source code managed by some company, as her reputation increases. Such rights may be review or modify code at different levels. Our first domain then is the Authorization domain and the use of reputation for fine-grained access control. In Section 2 we present some models which use reputation as part of a user identity and consider it in making access control decisions.

The second aspect we examine is Aggregation. Most reputation computational models use some form of aggregation of ratings to compute the reputation [START_REF] Jøsang | A survey of trust and reputation systems for online service provision[END_REF]. However, such aggregation is usually done within a single community. In real-life, users may be active in several communities and to protect their privacy, users may use different identities in different communities. A major shortcomings is that user efforts to gain a good reputation in one community are not utilized in other communities they are active in. Another shortcoming is the inability of one community to learn about the dishonest behavior of some member as identified by other communities. Thus the need arises to aggregate reputation from multiple communities. We developed the Cross-Community Reputation (CCR) model for the sharing of reputation knowledge across virtual communities [START_REF] Gal-Oz | Sharing reputation across virtual communities[END_REF][START_REF] Gal-Oz | Cross-community reputation: Policies and alternatives[END_REF][START_REF] Grinshpoun | CCR: A model for sharing reputation knowledge across virtual communities[END_REF]. The CCR model is aimed at leveraging reputation data from multiple communities to obtain more accurate reputation. It enables new virtual communities to rapidly mature by importing reputation data from related communities. The use of Aggregation in the CCR model is discussed in Section 3.

The third aspect we discuss is Transitivity, an important property of trust which has implications on the computation of reputation. It enables us to compute reputation not only from our own experience or our friends experience but also from our "friends of friends" experience, etc. Several flow models for computing reputation while practicing the transitivity property, have been published, including Eigen-trust [START_REF] Kamvar | The eigentrust algorithm for reputation management in p2p networks[END_REF] and Page-rank [START_REF] Parreira | Efficient and decentralized pagerank approximation in a peer-to-peer web search network[END_REF]. Our unique contribution here is in transferring these ideas to the computation of Internet domains reputation. Today's internet world is full of threats and malware. Hackers often use various domains to spread and control their malware. The detection of these misbehaving domains is difficult since there is no time to collect and analyze traffic data in real-time, thus their identification ahead of time is very important. We use the term domain reputation to express a measure of our belief that a domain is benign or malicious. Computing domain reputation by using the Transitivity property and a Flow algorithm was investigated by us [START_REF] Mishsky | A flow based domain reputation model[END_REF] and will be discussed in Section 3.

Identity Reputation and Access Control

Conventional access control models like role based access control are suitable for regulating access to resources by known users. However, these models have often found to be inadequate for open and decentralized multi-centric systems where the user population is dynamic and the identity of all users are not known in advance. For such systems, there must be, in addition to user authentication, some trust measure associated with the user. Such trust measure can be represented by the user reputation as one attribute of its identity. Chakraborty and Ray [START_REF] Chakraborty | Trustbac: integrating trust relationships into the rbac model for access control in open systems[END_REF] presented TrustBAC, a trust based access control model. It extends the conventional role based access control model with the notion of trust levels. Users are assigned to trust levels instead of roles based on a number of factors like user credentials, user behavior history, user recommendation etc. Trust levels are assigned to roles which are assigned to permissions as in role based access control. In Trustbac, when the reputation of a user decreases because of past actions, its assignment to the original role may not be valid anymore and a new role with less permissions is assigned by the system. An example of such scenario in the digital library domain is given in [START_REF] Chakraborty | Trustbac: integrating trust relationships into the rbac model for access control in open systems[END_REF]. The switching of roles may not be desirable in all cases. In a medical domain for example, a physician with less reputation may not lose its role as "doctor" but may lose instead some of her permissions. This dynamic assignment of permissions for the same role, based on the user reputation may be much more flexible and can prevent the proliferation of too many roles. In [START_REF] Lavi | A dynamic reputation based rbac model[END_REF] we define this dynamic model formally and show a detailed example of its operation in the software development domain. The main observation of this is that when one considers reputation as part of the user identity, one can support much more flexible role-based models without the need to increase significantly the number of roles in the system.

Aggregation and Cross Community Reputation

In this section we briefly describe the way reputation is aggregated from several communities using the CCR model [START_REF] Grinshpoun | CCR: A model for sharing reputation knowledge across virtual communities[END_REF][START_REF] Gal-Oz | Sharing reputation across virtual communities[END_REF]. The CCR model defines the major stages required to aggregate the reputation of a community member with the reputation of that member in other communities. The first stage determines the confidence one community has in another as a precondition for receiving reputation information from the latter. The second stage involves the conversion of reputation values from the domain values of one community to those of the other. In the third stage, a matching procedure is carried out between the sets of attributes used by the participating communities to describe reputation.

As an example, suppose there are two sport communities in which a commentator is active, one for Basketball, the other for Football. Assume that Bob a commentator likes to import (and aggregate) his reputation from the football community into the basketball community. The first stage considers the general confidence that basketball community members have for reputation computed in the football community. The second stage considers the statistical distribution of reputation values in the two communities and apply the required transformation (e.g., a very good rating in one community may only be considered "good" in the other). The third stage maps the specific attributes that are used to compute the reputation in the two communities (e.g., the attribute "prediction accuracy" in the football community may be partially mapped to the attribute "general reliability" in the basketball community). A detailed mathematical model which explains the process of the mapping and aggregation of CCR, is described in [START_REF] Gal-Oz | Sharing reputation across virtual communities[END_REF]. The CCR model was implemented as the TRIC software. TRIC is concerned primarily with aggregating different reputation mechanisms across communities and with protecting user rights to privacy and control over data during this aggregation. The CCR computation process [START_REF] Gal-Oz | Sharing reputation across virtual communities[END_REF] begins when a requesting community that wishes to receive CCR data regarding one of its users, sends a request to relevant responding communities. Communities that have reputation data of the user and are willing to share the information reply with the relevant reputation data. The received data is aggregated and assembled into an object containing the CCR data of the user in the context of the requesting community. This process is illustrated in Figure 1. One of the important goals associated with sharing reputation between communities is dealing with privacy. Within the CCR model, we identified three major privacy concerns that are not present or that are less significant in single community domains. First Unlinkability is a primary concern raised by the CCR model. Although we aim to compute a user's CCR from several communities, we provide the means to do so without compromising the user's anonymity in each community and while upholding the requirement of unlinkability between the communities. Controlling the dissemination of reputation information is another privacy requirement. We present a policy-based approach that enables both the users and the communities to have control over the dissemination of reputation data. The third privacy issue we address is the tradeoff between privacy and trust. We suggest the transparency measure for evaluating CCR objects. To attain a high transparency rank, members are encouraged to disclose their reputation-related information whenever it is clear that disclosing their information is preferable and more valuable to them than the potential impairment of their privacy. The issue of Privacy within the CCR model is discussed in [START_REF] Gal-Oz | Privacy issues with sharing reputation across virtual communities[END_REF].

Transitivity and Computing Domains Reputation

As was discussed earlier, computing domain reputation and identifying suspicious domains is a very important problem in Internet security today. Our approach to the problem [START_REF] Mishsky | A flow based domain reputation model[END_REF] uses a graph of domains and IPs which is constructed from mapping information available in DNS log records. The Domain Name Service (DNS) maps domain names to IP addresses and provides an essential service to applications on the internet. Many botnets use a DNS service to locate their next Command and Control ( C&C) site. Therefore, DNS logs have been used by several researchers to detect suspicious domains and filter their traffic if necessary. We take the famous expression Tell me who your friends are and I will tell you who you are, motivating many social trust models, into the internet domains world. Thus a domain that is related to malicious domains is more likely to be malicious as well. This Transitivity property motivates the use of a Flow algorithm. Although DNS data was used by several researchers before to compute domain reputation (see [START_REF] Antonakakis | Building a dynamic reputation model for dns[END_REF]), in [START_REF] Mishsky | A flow based domain reputation model[END_REF] we present a new approach by applying a flow algorithm on the DNS graph to obtain the reputation of domains and identify potentially malicious ones. Computing reputation for domains raises several new difficulties:

-Rating information if exists, is sparse and usually binary, a domain is labeled either "white" or "black" -Static sources like blacklists and whitelists are often not up-to-date -There is no explicit concept of trust between domains which makes it difficult to apply a flow or a transitive trust algorithm. -Reputation of domains is dynamic and changes very fast These difficulties make the selection of an adequate computational model for computing domain reputation a challenging task. Our approach is based on a flow algorithm, commonly used for computing trust in social networks and virtual communities. We are mainly inspired by two models: the Eigentrust model [START_REF] Kamvar | The eigentrust algorithm for reputation management in p2p networks[END_REF] which computes trust and reputation by transitive iteration through chains of trusting users and the model by Guha et al. [START_REF] Guha | Propagation of trust and distrus[END_REF] which combines the flow of trust and distrust. The motivation for using a flow algorithm is the assumption that IPs and domains which are neighbors of malware generating IPs and domains, are more likely to become malware generating as well. We construct a graph which reflects the topology of domains and IPs and their mappings and relationships and use a flow model to propagate the knowledge received in the form of black list, to label domains in the graph as malicious or suspected domains. Although we do not claim that every domain (or IP) connected to a malicious domain in our graph is malicious, our research hypothesis is that such domains(IPs) have a higher probability to become malicious. Our preliminary experimental results support this hypothesis.

The main input to the flow algorithm is the Domains/IPs graph. This graph is built from the following sources: 1) A-records: a database of successful mappings between IPs and domains, collected from a large ISP over several months. These mapping basically construct the edges between Domains and IPs. 2) Whois: a query and response protocol that is widely used for querying databases that store the registered users or assigners of an Internet resource. This database groups IPs which have similar characteristics and is therefore the base for IP to IP edges. In addition there are Domain to Domain edges which are related to similarity between domain names. 3) Feed-framework: a list of malicious domains which is collected over the same period of time as the collected A-records. This list is used as the initial "malicious" domains set. 4) Alexa: Alexa database ranks websites based on a combined measure of page views and unique site users. The initial "benign" domains is derived from this list. 5) VirustTotal: a website that provides free checking of domains for viruses and other malware. We use it to test our results as will be described below. The most difficult part in constructing the Domain/IP graph is assigning the weight on the edges, since the weight is proportional to the amount of flow on the edge. We tested several methods to assign weights which consider topologies of the graph and other factors, see [START_REF] Mishsky | A flow based domain reputation model[END_REF]. Once the DNS graph is built and the sets of "benign" and "malicious" domains are extracted, the algorithm can be performed. The entire process is depicted in Figure 2.

The flow algorithm models the idea that each IP or domain distribute their reputation to IPs or domains connected to them. This is done iteratively and the reputation in each iteration is added to the total reputation of a domain or IP, with some attenuation factor. The attenuation factor is a means to reduce the amount of reputation one vertex can gain from a vertex that is not directly connected to it by transitivity. The flow algorithm is executed separately to propagate good reputation and bad reputation and then the two reputation values are combined in several manners resulting with several variations of the algorithm (see details in [START_REF] Mishsky | A flow based domain reputation model[END_REF].) The important contribution of these algorithms is their ability to correctly predict future malicious domains. Although not all maliciouse domains are identified, a significant amount is discovered. In one of the experiments we used DNS logs over a 3 months period from which a large Domain-IP graph was constructed (close to one milion nodes!), and the flow algorithm was applied to it. The results were that out of the top 1000 highly suspected domains, 30% were found to be known malicious (using VirusTotal), while in a random set of 1000 domains only 0.9% were known as malicious.

Conclusions

Reputation is a key concept in making decisions in our social life. In this paper we have discussed three key aspects of reputation: Identity, Aggregation and Transitivity which are important when migrating the concept of reputation from one domain to another. This was shown by briefly reviewing several research papers of ours. The main conclusion is that reputation plays a major role in a wide range of domains beside the social arena domain.

Fig. 1 :

 1 Fig. 1: Request for CCR scenario: (1): A requesting community sends TRIC a request for the CCR of a community member; (2): TRIC compiles a request and (3) submits it to all potential responding communities; (4): Responding communities submit a reputation object of the member at subject; (5): TRIC processes all reputation objects and compiles a CCR object; (6): TRIC sends the CCR object to the requesting community

Fig. 2 :

 2 Fig.2:The process for computing the score: (1) Create the graph and assign weights represented as matrix; (2) Create the initial vector used for propagation;(3) Combine the matrix and the vector to execute the flow algorithm; (4) Get the final scores.