13005280
High dynamic range volume visualization
High resolution volumes require high precision compositing to preserve detailed structures. This is even more desirable for volumes with high dynamic range values. After the high precision intermediate image has been computed, simply rounding up pixel values to regular display scales loses the computed details. In this paper, we present a novel high dynamic range volume visualization method for rendering volume data with both high spatial and intensity resolutions. Our method performs high precision volume rendering followed by dynamic tone mapping to preserve details on regular display devices. By leveraging available high dynamic range image display algorithms, this dynamic tone mapping can be automatically adjusted to enhance selected features for the final display. We also present a novel transfer function design interface with nonlinear magnification of the density range and logarithmic scaling of the color/opacity range to facilitate high dynamic range volume visualization. By leveraging modern commodity graphics hardware and out-of-core acceleration, our system can produce an effective visualization of huge volume data.
2315502
SMARTPAPER: An Interactive and User Friendly Sketching System
This paper describes an interactive sketching system for 3D design/modeling that diverts from the conventional menu-and-button interfaces of CAD tools. The system, dubbed SMARTPAPER, offers a unified sketching environment that supports direct sketching as well as gestured sketching with more emphasis on the former to encourage natural sketching styles. SMARTPAPER also provides a unified 2D and 3D drawing domain by allowing the user to sketch directly on a 3D model in addition to the usual 2D sketching from scratch. A natural sketching experience is offered by supporting casual sketching consisting of wiggly, discontinuous, overlapping strokes. The system is empowered by an array of seamlessly integrated 2D and 3D features such as 2D sketch cleaning, 3D reconstruction from 2D sketch, 3D transformations, sketching on 3D, and conventional 3D CSG operations like cutting and joining. The key to the success of SMARTPAPER is efficient and robust 3D reconstruction from a single freehand 2D sketch with minimal hints. We have employed and improved Lipson’s optimization method, originally designed for offline reconstruction of engineering drawings, in our interactive system by leveraging additional clues obtained by interaction during sketching.
6763688
Paint Inspired Color Mixing and Compositing for Visualization
Color is often used to convey information, and color compositing is often required while visualizing multiattribute information. This paper proposes an alternative method for color compositing. In order to present understandable color blending to the general public, several techniques are proposed. First, a paint-inspired RYB color space is used. In addition, noise patterns are employed to produce subregions of pure color within an overlapped region. We show examples to demonstrate the effectiveness of our technique for visualization
1693128
LOD-sprite technique for accelerated terrain rendering
We present a novel rendering technique, termed LOD-sprite rendering, which uses a combination of a level-of-detail (LOD) representation of the scene together with reusing image sprites (previously rendered images). Our primary application is accelerating terrain rendering. The LOD-sprite technique renders an initial frame using a high-resolution model of the scene geometry. It renders subsequent frames with a much lower-resolution model of the scene geometry and texture-maps each polygon with the image sprite from the initial high-resolution frame. As it renders these subsequent frames, the technique measures the error associated with the divergence of the view position from the position where the initial frame was rendered. Once this error exceeds a user-defined threshold, the technique re-renders the scene from the high-resolution model. We have efficiently implemented the LOD-sprite technique with texture mapping graphics hardware. Although to date we have only applied LOD-sprite to terrain rendering, it could easily be extended to other applications. We feel LOD-sprite holds particular promise for real time rendering systems.
10605643
3D Volume Rotation Using Shear Transformations
We present a group of methods for decomposing an arbitrary 3D volume rotation into a sequence of simple shear (i.e., regular shift) operations. We explore different types of shear operations: 2Dbeam shear, a shear in one coordinate based on the other two coordinates; 2Dslice shear, a shear of a volume slice (in two coordinates) according to the third coordinate; and 2Dslice?beam shear, the combination of a beam shear and a slice shear. We show that an arbitrary 3D rotation can be decomposed into four 2D beam shears. We use this decomposition as a basis to obtain the sequence of 3D rotation decomposition into four 2D slice shears or three 2D slice?beam shears. Moreover, we observe that two consecutive slice shears can be achieved by shifting beams in 3D space, a transformation we call a 3D beam shear. Therefore, an arbitrary 3D rotation can be decomposed into only two 3D beam shears. Because of the regularity and simplicity of the shear operation, these decompositions are suitable for implementations on a multipipelined hardware or a massively parallel machine. In addition, we present a resampling scheme in which only a single-pass resampling is required for performing multiple-pass shears to achieve the 3D volume rotation.
7259311
Image-Based Rendering of Surfaces from Volume Data
We present an image-based rendering technique to accelerate rendering of surfaces from volume data. We cache the fully volume rendered image (called keyview) and use it to generate novel views without ray-casting every pixel. This is achieved by first constructing an underlying surface model of the volume and then texture mapping the keyview onto the geometry.When the novel view moves slightly away from the keyview, most of the original visible regions in the keyview are still visible in the novel view. Therefore, we only need to cast rays for pixels in the newly visible regions, which usually occupy only a small portion of the whole image, resulting in a substantial speedup. We have applied our technique to a virtual colonoscopy system and have obtained an interactive navigation speed through a 5123 size patient colon. Our experiments demonstrate an average of an order of magnitude speedup over that of traditional volume rendering, compromising very little on image quality.
1586078
Dual photography
We present a novel photographic technique called dual photography, which exploits Helmholtz reciprocity to interchange the lights and cameras in a scene. With a video projector providing structured illumination, reciprocity permits us to generate pictures from the viewpoint of the projector, even though no camera was present at that location. The technique is completely image-based, requiring no knowledge of scene geometry or surface properties, and by its nature automatically includes all transport paths, including shadows, inter-reflections and caustics. In its simplest form, the technique can be used to take photographs without a camera; we demonstrate this by capturing a photograph using a projector and a photo-resistor. If the photo-resistor is replaced by a camera, we can produce a 4D dataset that allows for relighting with 2D incident illumination. Using an array of cameras we can produce a 6D slice of the 8D reflectance field that allows for relighting with arbitrary light fields. Since an array of cameras can operate in parallel without interference, whereas an array of light sources cannot, dual photography is fundamentally a more efficient way to capture such a 6D dataset than a system based on multiple projectors and one camera. As an example, we show how dual photography can be used to capture and relight scenes.
13073706
Graph homotopy and Graham homotopy
Abstract Simple-homotopy for cell complexes is a special type of topological homotopy constructed by elementary collapses and elementary expansions. In this paper, we introduce graph homotopy for graphs and Graham homotopy for hypergraphs and study the relation between the two homotopies and the simple-homotopy for cell complexes. The graph homotopy is useful to describe topological properties of discretized geometric figures, while the Graham homotopy is essential to characterize acyclic hypergraphs and acyclic relational database schemes.
9470216
Quantization index modulation: A class of provably good methods for digital watermarking and information embedding
We consider the problem of embedding one signal (e.g., a digital watermark), within another "host" signal to form a third, "composite" signal. The embedding is designed to achieve efficient tradeoffs among the three conflicting goals of maximizing the information-embedding rate, minimizing the distortion between the host signal and composite signal, and maximizing the robustness of the embedding. We introduce new classes of embedding methods, termed quantization index modulation (QIM) and distortion-compensated QIM (DC-QIM), and develop convenient realizations in the form of what we refer to as dither modulation. Using deterministic models to evaluate digital watermarking methods, we show that QIM is "provably good" against arbitrary bounded and fully informed attacks, which arise in several copyright applications, and in particular it achieves provably better rate distortion-robustness tradeoffs than currently popular spread-spectrum and low-bit(s) modulation methods. Furthermore, we show that for some important classes of probabilistic models, DC-QIM is optimal (capacity-achieving) and regular QIM is near-optimal. These include both additive white Gaussian noise (AWGN) channels, which may be good models for hybrid transmission applications such as digital audio broadcasting, and mean-square-error-constrained attack channels that model private-key watermarking applications.
5122226
Sensor networks for medical care
Sensor networks have the potential to greatly impact many aspects of medical care. By outfitting patients with wireless, wearable vital sign sensors, collecting detailed real-time data on physiological status can be greatly simplified. However, there is a significant gap between existing sensor network systems and the needs of medical care. In particular, medical sensor networks must support multicast routing topologies, node mobility, a wide range of data rates and high degrees of reliability, and security. This paper describes our experiences with developing a combined hardware and software platform for medical sensor networks, called CodeBlue. CodeBlue provides protocols for device discovery and publish/subscribe multihop routing, as well as a simple query interface that is tailored for medical monitoring. We have developed several medical sensors based on the popular MicaZ and Telos mote designs, including a pulse oximeter, EKG and motion-activity sensor. We also describe a new, miniaturized sensor mote designed for medical use. We present initial results for the CodeBlue prototype demonstrating the integration of our medical sensors with the publish/subscribe routing substrate. We have experimentally validated the prototype on our 30-node sensor network testbed, demonstrating its scalability and robustness as the number of simultaneous queries, data rates, and transmitting sensors are varied. We also study the effect of node mobility, fairness across multiple simultaneous paths, and patterns of packet loss, confirming the system’s ability to maintain stable routes despite variations in node location and
4000958
A Better Heuristic for Preemptive Parallel Machine Scheduling with Batch Setup Times
This paper addresses the problem of scheduling N jobs on M identical parallel machines with the objective of minimizing the makespan. Jobs are divided into B batches. A sequence-independent batch setup time on a machine is incurred whenever the machine starts its processing on or switches it from a job in one batch to a job in another batch. On the basis of a heuristic for this NP-hard problem proposed by Monma and Potts, a modified heuristic that requires the same implementing time $O(N + (M + B)\log (M + B))$ and is asymptotically optimal is presented. Furthermore, for a certain class of problems, which includes the case in which each batch contains a single job, it has the worst-case performance ratio $\tau _M = \max \{ {\frac{{3M}}{{2M + 1}},\frac{{3M - 4}}{{2M - 2}}} \}$.