Towards Spontaneous Interaction with the 
Perceptive Workbench, a Semi-Immersive Virtual Environment

Abstract

1. Introduction

An additional problem is that any device held in the hand can become awkward while gesturing.  We have found this even with a simple pointing device, such as a stick with a few buttons [Seay99].  Also a user, unless fairly skilled, often has to pause to identify and select buttons on the stick.  With accurately tracked hands most of this awkwardness disappears.  We are adept at pointing in almost any direction and can quickly pinch fingers, for example, without looking at them.
Finally, physical objects are often natural interactors (such as phicons [Ullmer97]).  However, with current systems these objects must be inserted in advance or specially prepared.  One would like the system to accept objects that one chooses spontaneously for interaction.
 

Figure 1: A user interacting with Georgia Tech's Virtual Workbench using a 6DoF pointer.

2. Related Work

Fortunately, the computer vision community has taken up the task of tracking the user's hands and identifying gestures.  While generalized vision systems track the body in room and desk-based scenarios for games, interactive art, and augmented environments [Bobick96, Wren95, Wren97], reconstruction of fine hand detail involves carefully calibrated systems and is computationally intensive [Rehg93]. Even so, complicated gestures such as those used in sign language [Starner98, Vogler98] or the manipulation of physical objects [Sharma97] can be recognized. The Perceptive Workbench uses computer vision techniques to maintain a wireless interface.

Most directly related to the Perceptive Workbench, the "Metadesk" [Ullmer97] identifies and tracks objects placed on the desk's display surface using a near-infrared computer vision recognizer, originally designed by Starner. Unfortunately, since not all objects reflect infrared light and infrared shadows are not used, objects often need infrared reflective "hot mirrors" placed in patterns on their bottom surfaces to aid tracking and identification. Similarly, Rekimoto and Matsushita's "Perceptual Surfaces" [Rekimoto97] employ 2D barcodes to identify objects held against the "HoloWall" and "HoloTable." In addition, the HoloWall can track the user's hands (or other body parts) near or pressed against its surface, but its potential recovery of the user's distance from the surface is relatively coarse compared to the 3D pointing gestures of the Perceptive Workbench. Davis and Bobick's SIDEshow [Davis98] is similar to the Holowall except that it uses cast shadows in infrared for full-body 2D gesture recovery. Some augmented desks have cameras and projectors above the surface of the desk and are designed to augment the process of handling paper or interacting with models and widgets through the use of fiducials or barcodes [Arai95, Kobayashi98, Underkoffler98, Wellner93]. Krueger's VIDEODESK [Krueger91], an early desk-based system, used an overhead camera and a horizontal visible light table (for high contrast) to provide hand gesture input for interactions displayed on a monitor on the far side of the desk. In contrast with the Perceptive Workbench, none of these systems address the issues of introducing spontaneous 3D physical objects into the virtual environment in real-time and combining 3D deictic (pointing) gestures with object tracking and identification.
 
 

3. Apparatus

Figure 2: Light and camera positions for the Perceptive Workbench. 
The top view shows how shadows are cast and the 3D arm position is tracked. 

A ring of seven similar light-sources is mounted on the ceiling surrounding the desk (Figure 2). Each computer-controlled light casts distinct shadows on the desk's surface based on the objects on the table (Figure 3a). A second camera, this one in color, is placed next to the desk to provide a side view of the user's arms (Figure 3b). This side camera is used solely for recovering 3D pointing gestures.
 

Figure 3: Images seen by the infrared and color cameras: (a) arm shadow from ceiling IR lights; 
(b) image from side camera

   
We decided to use near-infrared light since it is invisible to the human eye.  Thus, illuminating the scene with it does not interfere with the user's interaction. Neither the illumination from the IR light sources underneath the table, nor the shadows cast from the overhead lights can be observed by the user.  On the other hand, IR light can still be seen by most standard CCD cameras.  This makes it a very inexpensive method for observing the interaction. In addition, by equipping the camera with an infrared filter, the camera image can be analyzed regardless of changes in (visible) scene lighting.

All vision processing is done on two SGI R10000 O2s (one for each camera), which communicate with a display client on an SGI Onyx via sockets.  However, the vision algorithms could also be run on one SGI with two digitizer boards or be implemented using inexpensive, semi-custom signal-processing hardware.
We use this setup for three different kinds of interaction which will be explained in more detail in the following sections: recognition and tracking of objects placed on the desk surface based on their contour, full 3D reconstruction of object shapes on the desk surface from shadows cast by the ceiling light-sources, and recognition and quantification of hand and arm gestures.

For display on the Perceptive Workbench, we use the Simple Virtual Environment Toolkit (SVE), a graphics and sound library developed by the Georgia Tech Virtual Environments Group [Kessler97].  SVE permits us to rapidly prototype applications used in this work.  In addition we use the workbench version of VGIS, a global terrain visualization and navigation system [Lindstrom96, Lindstrom97] as an application for interaction using hand and arm gestures. The workbench version of VGIS has stereoscopic rendering and an intuitive interface for navigation [Wartell99a, Wartell99b]. Both systems are built on OpenGL and have both SGI and PC implementations.
 
 

4. Object Tracking & Recognition

To achieve this goal, we use an improved version of the technique described in Starner et al. [Starner00]. The underside of the desk is illuminated by two near-infrared light-sources (Figure 2). Every object close to the desk surface (including the user's hands) reflects this light and can be seen by the camera under the display surface (Figure 4). Using a combination of intensity thresholding and background subtraction, we extract interesting regions of the camera image and analyze them. The resulting blobs are classified as different object types based on a set of features, including area, eccentricity, perimeter, moments, and the contour shape.
 

Figure 4: Image of reflection from the IR lights underneath the desk, as seen from the infrared camera.

In this work, we are using the object recognition and tracking capability mainly for "cursor objects". Our focus is on fast and accurate position tracking, but the system may be trained on a different set of objects to be used as navigational tools or physical icons [Ullmer97]. A future project will explore different modes of interaction based on this technology.
 
 

5. Deictic Gesture Tracking

For navigation and object manipulation in a virtual environment, many gestures are likely to have a deictic component. It is usually not enough to recognize that an object should be rotated, but we will also need to know the desired amount of rotation. For object selection or translation, we want to specify the object or location of our choice just by pointing at it. For these cases, gesture recognition methods that only take the hand shape and trajectory into account will not be sufficient. We need to recover 3D information about the user's hand and arm in relation to his body.
 
In the past, this information has largely been obtained by using wired gloves or suits, or magnetic trackers [Bolt92, Bimber99]. Such methods provide sufficiently accurate results but rely on wires and have to be tethered to the user's body, or to specific interaction devices, with all the aforementioned problems. Our goal is to develop a purely vision-based architecture that facilitates unencumbered 3D interaction.

With vision-based 3D tracking techniques, the first issue is to determine which information in the camera image is relevant, i.e. which regions represent the user's hand or arm. This task is made even more difficult by variation in user clothing or skin color and by background activity. Although typically only one user interacts with the environment at a given time using traditional methods of interaction, the physical dimensions of large semi-immersive environments such as the workbench invite people to watch and participate.

In a virtual workbench environment, there are few places where a camera can be placed to provide reliable hand position information. One camera can be set up next to the table without overly restricting the available space for users, but if a similar second camera were to be used at this location, either multi-user experience or accuracy would be compromised. We have addressed this problem by employing our shadow-based architecture (as described in the hardware section). The user stands in front of the workbench and extends an arm over the surface. One of the IR light-sources mounted on the ceiling to the left of, and slightly behind the user, shines its light on the desk surface, from where it can be seen by the IR camera under the projector (see Figure 5). When the user moves his arm over the desk, it casts a shadow on the desk surface (see Figure 6a). From this shadow, and from the known light-source position, we can calculate a plane in which the user's arm must lie.
 

Figure 5: Principle of pointing direction recovery.

Obviously, the success of the gesture tracking capability relies very strongly on how fast the image processing can be done. It is therefore necessary to use simple algorithms. Fortunately, we can make some simplifying assumptions about the image content.
We must first recover arm direction and fingertip position from both the camera and the shadow image. Since the user is standing in front of the desk and the user's arm is connected to the user's body, the arm's shadow should always touch the image border. Thus our algorithm exploits intensity thresholding and background subtraction to discover regions of change in the image and searches for areas in which these touch the front border of the desk surface (which corresponds to the top border of the shadow image or the left border of the camera image). It then takes the middle of the touching area as an approximation for the origin of the arm (Figure 6b and Figure 7b). For simplicity we will call this point the "shoulder", although in most cases it is not. Tracing the contour of the shadow, the algorithm searches for the point that is farthest away from the shoulder and takes it as the fingertip. The line from the shoulder to the fingertip reveals the 2D direction of the arm.
 

Figure 6: (a) Arm shadow from overhead IR lights; (b) resulting contour with recovered arm direction.

Figure 7: (a) image from side camera; (b) arm contour (from similar image) with recovered arm direction.

Limitations

Another problem can be seen in Figure 7b, where segmentation based on color background subtraction detects both the hand and the change in the display on the workbench. A more recent implementation replaces the side color camera with an infrared spotlight and a monochrome camera equipped with an infrared-pass filter. By adjusting the angle of the light to avoid the surface of the desk or any other close objects, the user's arm is illuminated and made distinct from the background and changes in the workbench's display does not affect the tracking.

A bigger problem is caused by the actual location of the side camera. If the user extends both of his arms over the desk surface, or if more than one user tries to interact with the environment at the same time, the images of these multiple limbs can overlap and be merged to a single blob. As a consequence, our approach will fail to detect the hand positions and orientations in these cases. A more sophisticated approach using previous position and movement information could yield more reliable results, but we chose, at this first stage, to accept this restriction and concentrate on high frame rate support for one-handed interaction. This may not be a serious limitation for a single user for certain tasks; a recent study shows that for a task normally requiring
two hands in a real environment, users have no preference for one versus two hands in a virtual environment that does not
model effects such as gravity and inertia [Seay99].
 
 

6. 3D Reconstruction

Figure 8: Real object inserted into the virtual world.

However, the necessity to move either the camera or the object imposes severe constraints on the working environment. To reconstruct an object with these methods, it is usually necessary to interrupt the user's interaction with it, take the object out of the user's environment, and place it into a specialized setting (sometimes in a different room). Other approaches make use of multiple cameras from different view points to avoid this problem at the expense of more computational power to process and communicate the results.
In this project, using only one camera and the infrared light sources, we analyze the shadows cast on the object from multiple directions (see Figure 9). As the process is based on infrared light, it can be applied independently of the lighting conditions and without interfering with the user's natural interaction with the desk.

The existing approaches to reconstruct shape from shadows or silhouettes can be divided into two camps. The volume approach, pioneered by Baumgart [Baumgart74] intersects view volumes to create a representation for the object. Common representations for the resulting model are polyhedra [Baumgart74, Conolly89], or octrees [Srivastava90, Chien86]. The surface approach reconstructs the surface as the envelope of its tangent planes. It has been realized in several systems [Boyer96, Seales95]. Both approaches can be combined, as in Sullivan's work [Sullivan98], which uses volume intersection to create an object and then smooths the surfaces with splines.

We have chosen to use a volume approach to create polyhedral reconstructions for several reasons. We want to create models that can be used instantaneously in a virtual environment. Our focus is not on getting a photorealistic reconstruction, but on creating a quick low polygon-count model for an arbitrary real-world object in real-time, without interrupting the ongoing interaction. Polyhedral models offer significant advantages over other representations, such as generalized cylinders, superquadrics, or polynomial splines. They are simple and computationally inexpensive, Boolean set operations can be performed on them with reasonable effort, and most current VR engines are optimized for fast rendering of polygonal scenes. In addition, polyhedral models are the basis for many later processing steps. If desired, they can still be refined with splines using a surface approach.
 

Figure 9: Principle of the 3D reconstruction.

Our approach is fully automated and does not require any special hardware (e.g. stereo cameras, laser range finders, structured lighting, etc.).  The method is extremely inexpensive, both in hardware and in computational cost. In addition, there is no need for extensive calibration, which is usually necessary in other approaches to recover the exact position or orientation of the object in relation to the camera.  We only need to know the approximate position of the light-sources (+/- 2 cm), and we need to adjust the camera to reflect the size of the display surface, which must be done only once.  Neither the camera, light-sources, nor the object are moved during the reconstruction process.  Thus recalibration is unnecessary.  We have substituted for all mechanical moving parts, which are often prone to wear and imprecision, by a series of light beams from known locations.

An obvious limitation for this approach is that we are confined to a fixed number of different views from which to reconstruct the object. The turntable approach, on the other hand, allows the system to take an arbitrary number of images from different view points.  However, Sullivan's work [Sullivan98] and our experience with our system have shown that even for quite complex objects, usually seven to nine different views are enough to get a reasonable 3D model of the object.  Note that the reconstruction uses the same hardware as the deictic gesture tracking capability discussed in the previous section.  Thus, it comes at no additional cost.

The speed of the reconstruction process is mainly limited by the switching time of the light sources. Whenever a new light-source is activated, the image processing system has to wait for several frames to receive a valid image. The camera under the desk records the sequence of shadows cast by an object on the table when illuminated by the different lights. Figure 10 shows two series of contour shadows extracted from two sample objects by using different IR sources. By approximating each shadow as a polygon (not necessarily convex) [Rosin95], we create a set of polyhedral "view cones", extending from the light source to the polygons. The intersection of these cones creates a polyhedron that roughly contains the object. Figure 11 shows some more shadows with the resulting polygons and a visualization of the intersection of polyhedral cones.
 

Figure 10: Shadow contours and interpolated polygons from a watering can (left) and a teapot (right).

Figure 11: Steps of 3D object reconstruction including extraction of contour shapes from shadows 
and intersection of multiple view cones (bottom).

Figure 12: 3D reconstruction of the watering can seen in Figure 5-5 (top) and a teapot (bottom).  
The colors are chosen to highlight the model faces.

Limitations

Exceptions are spherical or cylindrical objects.  The quality of reconstruction for these objects depends largely on the number of available views. With only seven light-sources, the resulting model will appear faceted.  This problem can be solved by either adding more light-sources, or by improving the model with the help of splines.

Apart from this, the accuracy by which objects can be reconstructed is bounded by another limitation of our architecture.  All our light-sources are mounted to the ceiling.  From this point of view they cannot provide full information about the object's shape.  There is a pyramidal "blind spot" above all horizontal flat surfaces that the reconstruction cannot eliminate.  The slope of these pyramids depends on the angle between the desk surface and the rays from the light-sources.  For our current hardware setting, this angle ranges between 37° and 55°, depending on the light-source.  Only structures with a greater slope will be reconstructed entirely without error.  This problem is intrinsic to the method and does also occur with the turntable approach, but on a much smaller scale.
 
We expect that we can greatly reduce the effects of this error by using the image from the side camera and extracting an additional silhouette of the object from this point of view.  This will help to keep the error angle well below 10°.  Calculations based on the current position of the side camera (optimized for the gesture recognition) promise an error angle of only 7°.

In the current version of our software, an additional error is introduced through the fact that we are not yet handling holes in the shadows.  But this is merely an implementation issue, which will be resolved in a future extension to our project.
 

7. Performance Analysis

Object and Gesture Tracking

Even so, we expect that simple improvements in the socket communication between the vision and rendering code and in the vision code itself will improve latency significantly.  For the terrain navigation task below, rendering speed provides a limiting factor.  However, Kalman filters may compensate for render lag and will also add to the stability of the tracking system.
 

3D Reconstruction

To measure error, we used the Metro tool [Cignoni98].  It approximates the real distance between the two surfaces by choosing a set of (100,000-200,000) points on the reconstructed surface, and then calculating the two-sided distance (Hausdorff distance) between each of these points and the ideal surface.  This distance is defined as

with E(S1,S2) denoting the one-sided distance between the surfaces S1 and S2:

The Hausdorff distance directly corresponds to the reconstruction error.  In addition to the maximum distance, we also calculated the mean and mean square distances.  Table 1 shows the results.  In these examples, the relatively large maximal error was caused by the difficulty in accurately reconstructing the tip of the cone and the pyramid.
 

8. Putting It to Use: Spontaneous Gesture Interfaces

When the user moves his hand above the display surface, the hand and arm are tracked as described in Section 4. A cursor appears at the projected hand position on the display surface, and a ray emanates along the projected arm axis. These can be used in selection or manipulation, as in Figure 13a. When the user places an object on the surface, the cameras recognize this and identify and track the object. A virtual button also appears on the display (indicated by the arrow in Figure 13b). Through shadow tracking, the system determines when the hand overlaps the button, selecting it. This action causes the system to capture the 3D object shape, as described in Section 5.
 

Figure 13: (a) Pointing gesture with hand icon and selection ray; (b) Virtual button 
rendered on the screen when object is detected on the surface.

This set provides the elements of a perceptual interface, operating without wires and without restrictions as to objects employed. For example, we have constructed a simple application where objects placed on the desk are selected, reconstructed, and then placed in a "template" set, displayed as slowly rotating objects on the left border of the workbench display. These objects can then be grabbed by the user and could act as new physical icons that are attached by the user to selection or manipulation modes. Or the shapes themselves could be used in model-building or other applications.
 

An Augmented Reality Game

Figure 14: (a) Two game masters controlling virtual monsters; (b) hardware outfit worn by mobile player.

Figure 15: (a) Mobile player performing Kung-Fu gestures to ward off monsters; 
(b) Virtual monsters overlayed on the real background as seen by the mobile player.

3D Terrain Navigation

Although there are currently some problems with latency and accuracy (both of which will be diminished in the future), a user can successfully employ gestures for navigation.  In addition the set of gestures are quite natural to use.  Further, we find that the vision system can distinguish hand articulation and orientation quite well.  Thus we will be able to attach interactions to hand movements (even without the larger arm movements). At the time of this writing, an HMM framework has been developed to allow the user to train his own gestures for recognition. This system, in association with the terrain navigation database, should allow more sophisticated interactions in the future.

Figure 16: Terrain navigation using deictic gestures: (a) panning; (b) rotation (about an axis perpendicular to 
and through the end of the rotation lever); (c) zooming in.

Telepresence, CSCW

Figure 17: An example for a telepresence system: A virtual instantiation of the workbench   
mirroring, in real-time, the type and position of objects placed on the real desk.

9. Future Work and Conclusions

In conclusion, the Perceptive Workbench uses a vision-based system to enable a rich set of interactions, including hand and arm gestures, object recognition and tracking, and 3D reconstruction of objects placed on its surface.  These elements are combined seamlessly into the same interface and can be used in diverse applications. In addition, the sensing system is relatively inexpensive, retailing approximately $1000 for the cameras and lighting equipment plus the cost of a computer with one or two video digitizers, depending on the functions desired.  As seen from the multiplayer gaming and terrain navigation applications, the Perceptive Workbench provides an untethered and spontaneous interface that encourages the inclusion of physical objects in the virtual environment.

Acknowledgements

References