Virtual assembly of complex objects has application in domains ranging from surgery planning to archaeology. In these domains the objective is to plan the restoration of skeletal anatomy or archaeological artifacts to achieve an optimal reconstruction without causing further damage. While graphical modeling plays a central role in virtual assembly, visual feedback alone is often insufficient since object contact and penetration is difficult to discern due to occlusion. Haptics can improve an assembly task by giving feedback when objects collide, but precise fitting of fractured objects guided by delicate haptic cues similar to those present in the physical world requires haptic display transparency beyond the performance of today's systems. We propose a haptic alignment tool that combines a 6 Degrees of Freedom (DOF) attraction force with traditional 6 DOF contact forces to pull a virtual object towards a local stable fit with a fixed object. The object forces are integrated into a virtual coupling framework yielding a stable haptic tool. We demonstrate the use of our system on applications from both cranio-maxillofacial surgery and archaeology, and show that we can achieve haptic rates for fractured surfaces with over 5000 points.

Cancer diagnosis is based on visual examination under a microscope of tissue sections from biopsies. But whereas pathologists rely on tissue stains to identify morphological features, automated tissue recognition using color is fraught with problems that stem from image intensity variations due to variations in tissue preparation, variations in spectral signatures of the stained tissue, spectral overlap and spatial aliasing in acquisition, and noise at image acquisition. We present a blind method for color decomposition of histological images. The method decouples intensity from color information and bases the decomposition only on the tissue absorption characteristics of each stain. By modeling the charge-coupled device sensor noise, we improve the method accuracy. We extend current linear decomposition methods to include stained tissues where one spectral signature cannot be separated from all combinations of the other tissues' spectral signatures. We demonstrate both qualitatively and quantitatively that our method results in more accurate decompositions than methods based on non-negative matrix factorization and independent component analysis. The result is one density map for each stained tissue type that classifies portions of pixels into the correct stained tissue allowing accurate identification of morphological features that may be linked to cancer.

Image-based rendering (IBR) systems create photorealistic views of complex 3D environments by resampling large collections of images captured in the environment. The quality of the resampled images increases significantly with higher image capture density. Thus, a significant challenge in interactive IBR systems is to provide both fast image access along arbitrary viewpoint paths and efficient storage of large image data sets. We describe a compression scheme based on a spatial image hierarchy that meets the requirements of interactive IBR walkthroughs. By exploiting image coherence over the entire image capture plane, we achieve compression performance similar to traditional motion-compensated schema, e.g., MPEG, yet allow image access along arbitrary paths. Furthermore, by exploiting graphics hardware for image resampling, we achieve interactive display rates during IBR walkthroughs.

Image-based rendering (IBR) systems enable virtual walkthroughs of photorealistic environments by warping and combining reference images to novel viewpoints under interactive user control. A significant challenge in such systems is to automatically compute image correspondences that enable accurate image warping.In this paper, we describe a new algorithm for computing a globally consistent set of image feature correspondences across a wide range of viewpoints suitable for IBR walkthroughs. We first detect point features in a dense set of omnidirectional images captured on an eye-height plane. Then, we track these features from image to image, identifying potential correspondences when two features track to the same position in the same image. Among the potential correspondences, we select the maximal consistent set using a greedy graph-labeling algorithm.A key feature of our approach is that it exploits the multiple paths that can be followed between images in order to increase the number of feature correspondences between distant images. We demonstrate the benefits of this approach in a real-time IBR walkthrough system where novel images are reconstructed as the user moves interactively.

Estimation of human head orientation is important for a number of applications such as human-computer interaction, teleconferencing, virtual reality, and 3D audio rendering. We present a system for estimating human head orientation based on visual information. Two neural networks are trained to approximate the functions that map an image of a head to the orientation of the head. We obtain ground-truth data for training and testing from an electromagnetic tracking device worn by subjects. Our experimental results demonstrate orientation accuracy within 10/spl deg/ with the subject free to move about at distances of three to ten feet from the camera. The system is designed to be robust to illumination changes and it runs in real time.

A long-standing research problem in computer graphics is to reproduce the visual experience of walking through a large photorealistic environment interactively. On one hand, traditional geometry-based rendering systems fall short of simulating the visual realism of a complex environment. On the other hand, image-based rendering systems have to date been unable to capture and store a sampled representation of a large environment with complex lighting and visibility effects. In this paper, we present a "sea of images," a practical approach to dense sampling, storage, and reconstruction of the plenoptic function in large, complex indoor environments. We use a motorized cart to capture omnidirectional images every few inches on a eye-height plane throughout an environment. The captured images are compressed and stored in a multiresolution hierarchy suitable for real-time prefetching during an interactive walkthrough. Later, novel images are reconstructed for a simulated observer by resampling nearby captured images. Our system acquires 15,254 images over 1,050 square feet at an average image spacing of 1.5 inches. The average capture and processing time is 7 hours. We demonstrate realistic walkthroughs of real-world environments reproducing specular reflections and occlusion effects while rendering 15-25 frames per second.

We introduce a new paradigm for real-time conversion of a real world event into a rich multimedia database by processing data from multiple sensors observing the event. A real-time analysis of the sensor data, tightly coupled with domain knowledge, results in instant indexing of multimedia data at capture time. This yields semantic information to answer complex queries about the content and the ability to extract portions of data that correspond to complex actions performed in the real world. The power of such an instantly indexed multimedia database system, in content-based retrieval of multimedia data or in semantic analysis and visualization of the data, far exceeds that of systems which index multimedia data only after it is produced. We present LucentVision, an instantly indexed multimedia database system developed for the sport of tennis. This system analyzes video from multiple cameras in real time and captures the activity of the players and the ball in the form of motion trajectories. The system stores these trajectories in a database along with video, 3D models of the environment, scores, and other domain-specific information. LucentVision has been used to enhance live television and Internet broadcasts with game analyses and virtual replays in more than 250 international tennis matches.

As multiple video cameras and other sensors generate very large quantities of multimedia data in media productions and surveillance applications, a key challenge is to identify the relevant portions of the data and to rapidly retrieve the corresponding sensor data. Spatio-temporal activity maps serve as an efficient and intuitive graphical user interface for multimedia retrieval, particularly when the media streams are derived from multiple sensors observing a physical environment. We formulate the media retrieval problem in this context, and develop an architecture for interactive media retrieval by combining spatio-temporal "activity maps" with domain specific event information. Activity maps are computed from trajectories of motion of objects in the environment, which in turn are derived automatically by analysis of sensor data. We present an activity map based video retrieval system for the sport of tennis and demonstrate that the activity map based scheme significantly helps the user in a) discovering the relevant portions of the data, and b) non-linearly retrieving the corresponding media streams.

Interactive walkthrough applications require detailed 3D models to give users a sense of immersion in an environment. Traditionally these models are built using computer-aided design tools to define geometry and material properties. But creating detailed models is time-consuming and it is also difficult to reproduce all geometric and photometric subtleties of real-world scenes. Computer vision attempts to alleviate this problem by extracting geometry and photogrammetry from images of the real-world scenes. However, these models are still limited in the amount of detail they recover.

Realistic modeling of reverberant sound in 3D virtual worlds provides users with important cues for localizing sound sources and understanding spatial properties of the environment. Unfortunately, current geometric acoustic modeling systems do not accurately simulate reverberant sound. Instead, they model only direct transmission and specular reflection, while diffraction is either ignored or modeled through statistical approximation. However, diffraction is important for correct interpretation of acoustic environments, especially when the direct path between sound source and receiver is occluded.

Remote experience of sporting events has thus far been limited mostly to watching video and the scores and statistics associated with the sport. However, a fast-developing trend is the use of visualization techniques to give new insights into performance, style, and strategy of the players. Automated techniques can extract accurate information from video about player performance that not even the most skilled observer is able to discern. When presented as static images or as a three-dimensional virtual replay, this information makes viewing a game an entirely new and exciting experience. This paper presents one such sports visualization system called LucentVision, which has been developed for the sport of tennis. LucentVision uses real-time video analysis to obtain motion trajectories of players and the ball, and offers a rich set of visualization options based on this trajectory data. The system has been used extensively in the broadcast of international tennis tournaments, both on television and the Internet.

The goal in user interfaces is natural interactivity unencumbered by sensor and display technology. In this paper, we propose that a multi-modal approach using inverse modeling techniques from computer vision, speech recognition, and acoustics can result in such interfaces. In particular, we demonstrate a system for audio-visual tracking, showing that such a system is more robust, more accurate, more compact, and yields more information than using a single modality for tracking. We also demonstrate how such a system can be used to find the talker among a group of individuals, and render 3D scenes to the user.

Realistic acoustic modeling is essential for spatializing sound in distributed virtual environments where multiple networked users move around and interact visually and aurally in a shared vir-tual world. Unfortunately, current methods for computing accurate acoustical models are not fast enough for real-time auralization of sounds for simultaneously moving sources and receivers. In this pa-per, we present three new beam tracing algorithms that greatly ac-celerate computation of reverberation paths in a distributed virtual environment by taking advantage of the fact that sounds can only be generated or heard at the positions of “avatars ” representing the users. The priority-driven beam tracing algorithm performs a best-first search of a cell adjacency graph, and thus enables new termina-tion criteria with which all early reflection paths can be found very efficiently. The bidirectional beam tracing algorithm combines sets of beams traced from pairs of avatar locations to find reverbera-tion paths between them while requiring significantly less compu-tation than previous unidirectional algorithms. The amortized beam tracing algorithm computes beams emanating from box-shaped re-gions of space containing predicted avatar locations and re-uses those beams multiple times to compute reflections paths as each avatar moves inside the box. Cumulatively, these algorithms enable speedups of approximately two orders of magnitude over previous methods. They are incorporated into a time-critical multiprocess-ing system that allocates its computational resources dynamically in order to compute the highest priority reverberation paths between moving avatar locations in real-time with graceful degradation and adaptive refinement. Key Words: Virtual environment systems, virtual reality, acoustic modeling, auralization, beam tracing.

This paper develops real time tracking technology for sports broadcast applications. The specific sport chosen here is the game of tennis. The outputs of the tennis tracking system are spatio-temporal trajectories of motion of the players and the ball which can in turn provide a number of statistics about the game. For instance, the distance travelled by a player, the speed and the acceleration at any instant, as well as court coverage patterns can be obtained from the trajectories. The statistics so obtained can be visualized in compelling ways to enhance the appreciation of the athleticism and strategy involved in the sport. We present techniques for tracking the players and the ball in video obtained from stationary cameras. The problem is challenging as the tracking needs to be performed outdoors, players are fast-moving non-rigid objects, and the ball is a small object that can move at speeds in the range of 150 miles an hour. Player trajectories are obtained by dynamically clustering tracks of local features. Ball segmentation and tracking is based on shape and color features of the ball. Real time tracking results are presented on video recorded live by the authors in an international tennis tournament.

Virtual environment research has focused on interactive image generation and has largely ignored acoustic modeling for spatialization of sound.Yet, realistic auditory cues can complement and enhance visual cues to aid navigation, comprehension, and sense of presence in virtual environments.A primary challenge in acoustic modeling is computation of reverberation paths from sound sources fast enough for real-time auralization.We have developed a system that uses precomputed spatial subdivision and "beam tree" data structures to enable real-time acoustic modeling and auralization in interactive virtual environments.The spatial subdivision is a partition of 3D space into convex polyhedral regions (cells) represented as a cell adjacency graph.A beam tracing algorithm recursively traces pyramidal beams through the spatial subdivision to construct a beam tree data structure representing the regions of space reachable by each potential sequence of transmission and specular reflection events at cell boundaries.From these precomputed data structures, we can generate high-order specular reflection and transmission paths at interactive rates to spatialize fixed sound sources in real-time as the user moves through a virtual environment.Unlike previous acoustic modeling work, our beam tracing method: 1) supports evaluation of reverberation paths at interactive rates, 2) scales to compute highorder reflections and large environments, and 3) extends naturally to compute paths of diffraction and diffuse reflection efficiently.We are using this system to develop interactive applications in which a user experiences a virtual environment immersively via simultaneous auralization and visualization.

Neuroscientists have studied the relationship between nerve cell morphology and function for over a century. To pursue these studies, they need accurate three-dimensional models of nerve cells that facilitate detailed anatomical measurement and the identification of internal structures. Although serial transmission electron microscopy has been a source of such models since the mid 1960s, model reconstruction and analysis remain very time consuming. The authors have developed a new approach to reconstructing and visualizing 3D nerve cell models from serial microscopy. An interactive system exploits recent computer graphics and computer vision techniques to significantly reduce the time required to build such models. The key ingredients of the system are a digital "blink comparator" for section registration, "snakes," or active deformable contours, for semiautomated cell segmentation, and voxel-based techniques for 3D reconstruction and visualization of complex cell volumes with internal structures.

Digital filtering is a crucial operation in volume reconstruction and visualization. Lowpass filters are needed for subsampling and minification. Interpolation filters are needed for registration and magnification, and to compensate for geometric distortions introduced by scanners. Interpolation filters are also needed in volume rendering for ray-casting and slicing. In this paper, we describe a method for digital filter design of interpolation filters based on weighted Chebyshev minimization. The accuracy of the resulting filters are compared with some commonly used filters defined by piecewise cubic polynomials. A significant finding of this paper is that although piecewise cubic interpolation has some computational advantages and may yield visually satisfactory results for some data, other data result in artifacts such as blurring. Furthermore, piecewise cubic filters are inferior for operations such as registration. Better results are obtained by the filters derived in this papers at only small increases in computation.>

We briefly survey the major thrusts of computer graphics activities, examining trends and topics rather than offering a comprehensive survey of all that is happening. The directions of professional activities, hardware, software, and algorithms are outlined. Within hardware we examine workstations, personal graphics systems, high performance systems, and low level VLSI chips; within software, standards and interactive system design; within algorithms, visible surface rendering and shading, three-dimensional modeling techniques, and animation.

A set of quantitative performance modeling techniques for the evaluation and design of vector graphics system hardware and firmware is presented.The performance modeling techniques are based on a functional model of graphics processing.The techniques are used to evaluate different addressing schemes for graphical data, and the evaluation quantitatively demonstrates trade-offs between a versatile addressing scheme and one that permits only immediate data.

BUMPS (Brown University Multiple Projection System) is a program that illustrates the implementation of viewing transformations using animation. The program uses the viewing model defined in the Core Graphics System. BUMPS employs interactive computer graphics to demonstrate how planar geometric projections are generated, what the effects of different projections and projection parameters are on the projected object, and how the viewing functions of the Core Graphics System work. After presenting background material on projections, the features of BUMPS are described, followed by a pictorial user scenario of BUMPS in action. The paper concludes with a discussion of the merits of user controlled animation for teaching and possible improvements to the program.

The viewing scheme in the Core Graphics System is based on a unified approach to the specification of the viewing parameters for all types of planar geometric projections. As a result, the specification of some of the viewing parameters is inconsistent with traditional ways of specification and will often be found unnatural for use in certain application areas. Additionally, this choice of viewing parameters leads to inefficient implementations of viewing parameter modification, particularly in a high-performance graphics system which supports transformations in hardware or firmware.