Search

Video from aerial surveillance can provide a rich source of data for many applications and can be enhanced for display and analysis through such methods as mosaic construction, super-resolution, and mover detection. All of these methods require accurate frame-to-frame registration, which for live use must be performed in real time. In many situations, scene parallax may make alignment using global transformations impossible or error-prone, limiting the performance of subsequent processing and applications. For these cases, dense (per-pixel) correspondence is required, but this can be computationally prohibitive. This paper presents a hierarchical dense correspondence algorithm designed for implementation on graphics processing units (GPUs). Since the method does not rely on epipolar geometry, it is also suitable for use when there are uncor-rected nonlinear lens distortions. A framework for using this dense correspondence to implement local mosaicking, super-resolution enhancement, and mover detection is also presented and demonstrated using examples of each of these types of enhancement and different types of video sources.

A correspondence and camera error analysis for dense correspondence applications such as structure from motion is introduced. This provides error introspection, opening up the possibility of adaptively and progressively applying more expensive correspondence and camera parameter estimation methods to reduce these errors. The presented algorithm evaluates the given correspondences and camera parameters based on an error generated through simple triangulation. This triangulation is based on the given dense, non-epipolar constraint, correspondences and estimated camera parameters. This provides an error map without requiring any information about the perfect solution or making assumptions about the scene. The resulting error is a combination of correspondence and camera parameter errors. An simple, fast low/high pass filter error factorization is introduced, allowing for the separation of correspondence error and camera error. Further analysis of the resulting error maps is applied to allow efficient iterative improvement of correspondences and cameras.

We present two algorithms for data compression and occlusion culling that im- prove interactive, adaptive isosurface extraction from large volume datasets. Our algorithm, based on hierarchical tetrahedral meshes defined by longest edge bisection, allows arbitrary isosurfaces to be adaptively extracted at interactive rates from losslessly compressed volumes where the region of interest, determined at runtime by user interaction, is decompressed on- the-fly. For interactive applications, we exploit frame-to-frame coherence between consecutive views to simplify the mesh structure in occluded regions and eliminate occluded triangles sig- nificantly reducing the complexity of the visualized surface and the underlying multiresolution volume representation. We extend the use of hardware accelerated occlusion queries to adap- tive isosurface extraction applications where the surface geometry and topology change with the level-of-detail and view-point and the user can select an arbitrary isovalue for visualization.

This paper accompanies a poster that is being presented at the SciDAC 2006 meeting in Denver, CO. This project focuses on leveraging scientific visualization and analytics software technology as an enabling technology for increasing scientific productivity and insight. Advances incomputational technology have resulted in an "information big bang," which in turn has createda significant data understanding challenge. This challenge is widely acknowledged to be one of the primary bottlenecks in contemporary science. The vision for our Center is to respond directly to that challenge by adapting, extending, creating when necessary and deploying visualization and data understanding technologies for our science stakeholders. Using an organizational model as a Visualization and Analytics Center for Enabling Technologies (VACET), we are well positioned to be responsive to the needs of a diverse set of scientific stakeholders in a coordinated fashion using a range of visualization, mathematics, statistics, computer and computational science and data management technologies.

Analysis of the results obtained from material simulations is important in the physical sciences. Our research was motivated by the need to investigate the properties of a simulated porous solid as it is hit by a projectile. This paper describes two techniques for the generation of distance fields containing a minimal number of topological features, and we use them to identify features of the material. We focus on distance fields defined on a volumetric domain considering the distance to a given surface embedded within the domain. Topological features of the field are characterized by its critical points. Our first method begins with a distance field that is computed using a standard approach, and simplifies this field using ideas from Morse theory. We present a procedure for identifying and extracting a feature set through analysis of the MS complex, and apply it to find the invariants in the clean distance field. Our second method proceeds by advancing a front, beginning at the surface, and locally controlling the creation of new critical points. We demonstrate the value of topologically clean distance fields for the analysis of filament structures in porous solids. Our methods produce a curved skeleton representation of the filaments that helps material scientists to perform a detailed qualitative and quantitative analysis of pores, and hence infer important material properties. Furthermore, we provide a set of criteria for finding the "difference" between two skeletal structures, and use this to examine how the structure of the porous solid changes over several timesteps in the simulation of the particle impact.

The SciDAC2 Visualization and Analytics Center for Enabling Technologies (VACET) began operation on 10/1/2006. This document, dated 11/27/2006, is the first version of the VACET project management plan. It was requested by and delivered to ASCR/DOE. It outlines the Center's accomplishments in the first six weeks of operation along with broad objectives for the upcoming future (12-24 months).

Despite its fundamental importance for a broad range of applications, little is understood about the behaviour of metals during the initial phase of shock compression. Here, we present molecular dynamics (MD) simulations of shock-wave propagation through a metal allowing a detailed analysis of the dynamics of high strain-rate plasticity. Previous MD simulations have not seen the evolution of the strain from one- to three-dimensional compression that is observed in diffraction experiments. Our large-scale MD simulations of up to 352 million atoms resolve this important discrepancy through a detailed understanding of dislocation flow at high strain rates. The stress relaxes to an approximately hydrostatic state and the dislocation velocity drops to nearly zero. The dislocation velocity drop leads to a steady state with no further relaxation of the lattice, as revealed by simulated X-ray diffraction.

We describe the second of two large-scale atomic simulation projects on materials failure performed on the 12-teraflop ASCI (Accelerated Strategic Computing Initiative) White computer at the Lawrence Livermore National Laboratory. This investigation simulates ductile failure by using more than one billion atoms where the true complexity of the creation and interaction of hundreds of dislocations are revealed.

We describe the first of two large-scale atomic simulation projects on materials failure performed on the 12-teraflop ASCI (Accelerated Strategic Computing Initiative) White computer at Lawrence Livermore National Laboratory. This is a multimillion-atom simulation study of crack propagation in rapid brittle fracture where the cracks travel faster than the speed of sound. Our finding centers on a bilayer solid that behaves under large strain like an interface crack between a soft (linear) material and a stiff (nonlinear) material. We verify that the crack behavior is dominated by the local (nonlinear) wave speeds, which can be in excess of the conventional sound speeds of a solid.

In situ X‐ray diffraction allows the determination of the structure of transient states of matter. We have used laser‐plasma generated X‐rays to study how single crystals of metals (copper and iron) react to uniaxial shock compression. We find that copper, as a face‐centred‐cubic material, allows rapid generation and motion of dislocations, allowing close to hydrostatic conditions to be achieved on sub‐nanosecond timescales. Detailed molecular dynamics calculations provide novel information about the process, and point towards methods whereby the dislocation density might be measured during the passage of the shock wave itself. We also report on recent experiments where we have obtained diffraction images from shock‐compressed single‐crystal iron. The single crystal sample transforms to the hcp phase above a critical pressure, below which it appears to be uniaxially compressed bcc, with no evidence of plasticity. Above the transition threshold, clear evidence for the hcp phase can be seen in the diffraction images, and via a mechanism that is also consistent with recent multi‐ million atom molecular dynamics simulations that use the Voter‐ Chen potential. We believe these data to be of import, in that they constitute the first conclusive in situ evidence of the transformed structure of iron during the passage of a shock wave.

Summary form only given. We developed the piecewise-linear Haar (PLHaar) transform (Senecal, J.G. et al., Proc. 12th Pacific Conf. on Computer Graphics and Appl., p.371-80, 2004), an integer wavelet-like transform. PLHaar does not have dynamic range expansion, i.e., it is an n-bit to n-bit transform. To our knowledge, PLHaar is the only reversible n-bit to n-bit transform that is suitable for lossy and lossless coding. We are investigating PLHaar's use in lossy image coding. Preliminary results from thresholding transform coefficients show that PLHaar does not produce objectionable artifacts like previous n-bit to n-bit transforms, such as that of Honyang Chao et al. (CFH) (see Advances in Computational Mathematics, Lect. Notes In Pure and App. Math., vol.202, p.13-38, 1999). Also, at lower bitrates PLHaar images have increased contrast. For a given set of CFH and PLHaar coefficients with equal entropy, the PLHaar reconstruction is more appealing, although the PSNR may be lower.

We introduce the piecewise-linear Haar (PLHaar) transform, a reversible n-bit to n-bit transform that is based on the Haar wavelet transform. PLHaar is continuous, while all current n-bit to n-bit methods are not, and is therefore uniquely usable with both lossy and lossless methods (e.g. image compression). PLHaar has both integer and continuous (i.e. non-discrete) forms. By keeping the coefficients to n bits PLHaar is particularly suited for use in hardware environments where channel width is limited, such as digital video channels and graphics hardware.

We present an algorithm for adaptively extracting and rendering isosurfaces from compressed time-varying volume data sets. Tetrahedral meshes defined by longest edge bisection are used to create a multiresolution representation of the volume in the spatial domain that is adapted over time to approximate the time-varying volume. The reextraction of the isosurface at each time step is accelerated with the vertex programming capabilities of modern graphics hardware. A data layout scheme which follows the access pattern indicated by mesh refinement is used to access the volume in a spatially and temporally coherent manner. This data layout scheme allows our algorithm to be used for out-of-core visualization.

Arithmetic coding achieves a superior coding rate when encoding a binary source, but its lack of speed makes it an inferior choice when true high-performance encoding is needed. This paper presents the practical implementation of fast entropy coders for binary messages utilizing only bit shifts and table lookups. To limit code table size the proposed code lengths is limited with a type of variable-to-variable (VV) length code created from source string merging. This is referred to as "merged codes". With merged codes it is possible to achieve a desired level of speed by adjusting the number of bits read from the source at each step. The most efficient merged codes yield a coder with a worst-case inefficiency of 0.4%, relative to the Shannon entropy. Using a hybrid Golomb-VV bin coder the compression ratio that is competitive with other state-of-the-art coders, at a superior throughput is achieved.

We address the texture level-of-detail problem for extremely large surfaces such as terrain during realtime, view-dependent rendering. A novel texture hierarchy is introduced based on 4-8 refinement of raster tiles, in which the texture grids in effect rotate 45 degrees for each level of refinement. This hierarchy provides twice as many levels of detail as conventional quadtree-style refinement schemes such as mipmaps, and thus provides per-pixel view-dependent filtering that is twice as close to the ideal cutoff frequency for an average pixel. Because of this more gradual change in low-pass filtering, and due to the more precise emulation of the ideal cutoff frequency, we find in practice that the transitions between texture levels of detail are not perceptible. This allows rendering systems to avoid the complexity and performance costs of per-pixel blending between texture levels of detail. The 4-8 texturing scheme is integrated into a variant of the Real-time Optimally Adapting Meshes (ROAM) algorithm for viewdependent multiresolution mesh generation. Improvements to ROAM included here are: the diamond data structure as a stream-lined replacement for the triangle bintree elements, the use of low-pass- filtered geometry patches in place of individual triangles, integration of 4-8 textures, and a simple out-of-core data access mechanism for texture and geometry tiles.

We present a new construction of lifted biorthogonal wavelets on surfaces of arbitrary two-manifold topology for compression and multiresolution representation. Our method combines three approaches:subdivision surfaces of arbitrary topology, B-spline wavelets, and the lifting scheme for biorthogonal wavelet construction. The simple building blocks of our wavelet transform are local lifting operations performed on polygonal meshes with subdivision hierachy. Starting with a coarse, irregular polyhedral base mesh, our transform creates a subdivision hierarchy of meshes converging to a smooth limit surface. At every subdivision level, geometric detail can be expanded from wavelet coefficients and added to the surface. We present wavelet constuctions for bilinear, bicubic, and biquintic B-Spline subdivision. While the bilinear and bicubic constructions perform well in numerical experiments, the biquintic construction turns out to be unstable. For lossless compression, our transform can be computed in integer arithmetic, mapping integer coordinates of control points to integer wavelet coefficients. Our approach provides a highly efficient and progessive representation for complex geometries of arbitrary topology.

Multiresolution methods provide a means for representing data at multiple levels of detail. They are typically based on a hierarchical data organization scheme and update rules needed for data value computation. We use a data organization that is based on what we call \(\root n \of 2 \) subdivision, where n is the dimension of the data set. The main advantage of \(\root n \of 2 \) subdivision, compared to quadtree (n = 2) or octree (n = 3) organizations, is that the number of vertices is only doubled in each subdivision step instead of multiplied by a factor of 2 n , i. e., four or eight, respectively. To update data values we use n-variate B-spline wavelets, which yield better approximations for each level of detail. We develop a lifting scheme for n = 2 and n = 3 based on the \(\root n \of 2 \)-subdivision scheme. We obtain narrow masks that provide a basis for out-of-core techniques as well as view-dependent visualization and adaptive, localized refinement.

Methods of producing reversible n-bit to n-bit integer transforms is presented in this paper. Such methods are particularly suited for hardware-based implementations, as keeping the coefficients to n bits simplifies the design of custom hardware and makes it easier to use these approaches on preexisting hardware with limited channel width. One of our methods, called table-lookup Haar (TLHaar) is an approximation of the Haar integer wavelet transform (Haar IWT). The Haar IWT takes two integer data values A and B and using averaging and differencing produces a low-pass value L and a high-pass value H, both integers. The lookup tables are created by initializing each with an identity transform. TLHaar executes up to 44% faster. Compression results are mixed, and depend on the compression method used and the image type.

We introduce a novel wavelet decomposition algorithm that makes a number of powerful new surface design operations practical. Wavelets, and hierarchical representations generally, have held promise to facilitate a variety of design tasks in a unified way by approximating results very precisely, thus avoiding a proliferation of undergirding mathematical representations. However, traditional wavelet decomposition is defined from fine to coarse resolution, thus limiting its efficiency for highly precise surface manipulation when attempting to create new non-local editing methods.

We analyze a large-scale molecular dynamics simulation of work hardening in a ductile model material comprising of 500 million atoms interacting with a Lennard-Jones pair potential within a classical molecular dynamics scheme. With tensile loading, we observe emission of thousands of dislocations from two sharp cracks. The dislocations interact in a complex way, revealing three fundamental mechanisms of work-hardening. These are (1) dislocation cutting processes, jog formation and generation of point defects; (2) activation of secondary slip systems by cross-slip; and (3) formation of sessile Lomer-Cottrell locks. The dislocations self-organize into a complex sessile defect topology. Our analysis illustrates mechanisms formerly only known from textbooks and observed indirectly in experiment. It is the first time that such a rich set of fundamental phenomena has been seen in a single computer simulation.

Multiresolution methods for representing data at multiple levels of detail are widely used for large-scale two- and three-dimensional data sets. We present a four-dimensional multiresolution approach for time-varying volume data. This approach supports a hierarchy with spatial and temporal scalability. The hierarchical data organization is based on /sup 4//spl radic/2 subdivision. The /sup n//spl radic/2-subdivision scheme only doubles the overall number of grid points in each subdivision step. This fact leads to fine granularity and high adaptivity, which is especially desirable in the spatial dimensions. For high-quality data approximation on each level of detail, we use quadrilinear B-spline wavelets. We present a linear B-spline wavelet lifting scheme based on /sup n//spl radic/2 subdivision to obtain narrow masks for the update rules. Narrow masks provide a basis for out-of-core data exploration techniques and view-dependent visualization of sequences of time steps.

We present a surface compression method that stores surfaces as wavelet-compressed signed-distance volumes. Our approach enables the representation of surfaces with complex topology and arbitrary numbers of components within a single multiresolution data structure. This data structure elegantly handles topological modification at high compression rates. Our method does not require the costly and sometimes infeasible base mesh construction step required by subdivision surface approaches. We present several improvements over previous attempts at compressing signed-distance functions, including an O(n) distance transform, a zero set initialization method for triangle meshes, and a specialized thresholding algorithm. We demonstrate the potential of sampled distance volumes for surface compression and progressive reconstruction for complex high genus surfaces.

The trivariate tensor-product B-spline solid is a direct extension of the B-spline patch and has been shown to be useful in the creation and visualization of free-form geometric solids. Visualizing these solid objects requires the determination of the boundary surface of the solid, which is a combination of parametric and implicit surfaces. This paper presents a method that determines the implicit boundary surface by examination of the Jacobian determinant of the defining B-spline function. Using an approximation to this determinant, the domain space is adaptively subdivided until a mesh can be determined such that the boundary surface is close to linear in the cells of the mesh. A variation of the marching cubes algorithm is then used to draw the surface. Interval approximation techniques are used to approximate the Jacobian determinant and to approximate the Jacobian determinant gradient for use in the adaptive subdivision methods. This technique can be used to create free-form solid objects, useful in geometric modeling applications.

We present a new construction approach for symmetric lifted B-spline wavelets on irregular polygonal control meshes defining two-manifold topologies. Polygonal control meshes are recursively refined by stationary subdivision rules and converge to piecewise polynomial limit surfaces. At every subdivision level, our wavelet transforms provide an efficient way to add geometric details that are expanded from wavelet coefficients. Both wavelet decomposition and reconstruction operations are based on local lifting steps and have linear-time complexity.

Currently, large physics simulations produce 3D discretized field data whose individual isosurfaces, after conventional extraction processes, contain upwards of hundreds of millions of triangles. Detailed interactive viewing of these surfaces requires (a) powerful compression to minimize storage, and (b) fast view-dependent optimization of display triangulations to most effectively utilize high-performance graphics hardware. In this work, we introduce the first end-to-end multiresolution dataflow strategy that can effectively combine the top performing subdivision-surface wavelet compression and view-dependent optimization methods, thus increasing efficiency by several orders of magnitude over conventional processing pipelines. In addition to the general development and analysis of the dataflow, we present new algorithms at two steps in the pipeline that provide the “glue” that makes an integrated large-scale data visualization approach possible. A shrink-wrapping step converts highly detailed unstructured surfaces of arbitrary topology to the semi-structured meshes needed for wavelet compression. Remapping to triangle bintrees minimizes disturbing “pops” during realtime displaytriangulation optimization and provides effective selective-transmission compression for out-of-core and remote access to extremely large surfaces. Overall, this is the first effort to exploit semi-structured surface representations for a complete large-data visualization pipeline.

We present a new method for constructing multiresolution representations of data sets that contain material interfaces. Material interfaces embedded in the meshes of computational data sets are often a source of error for simplification algorithms because they represent discontinuities in the scalar or vector field over mesh elements. By representing material interfaces explicitly, we are able to provide separate field representations for each material over a single cell. Multiresolution representations utilizing separate field representations can accurately approximate datasets that contain discontinuities without placing a large percentage of cells around the discontinuous regions. Our algorithm uses a multiresolution tetrahedral mesh supporting fast coarsening and refinement capabilities; error bounds for feature preservation; explicit representation of discontinuities within cells; and separate field representations for each material within a cell.

This paper introduces the DesignersWorkbench, a semi-immersive virtual environment for two-handed modeling, sculpting and analysis tasks. The paper outlines the fundamental tools, design metaphors and hardware components required for an intuitive real-time modeling system. As companies focus on streamlining productivity to cope with global competition, the migration to computer-aided design (CAD), computer-aided manufacturing (CAM), and computer-aided engineering (CAE) systems has established a new backbone of modern industrial product development. However, traditionally a product design frequently originates from a clay model that, after digitization, forms the basis for the numerical description of CAD primitives. The DesignersWorkbench aims at closing this technology or ''digital gap'' experienced by design and CAD engineers by transforming the classical design paradigm into its filly integrated digital and virtual analog allowing collaborative development in a semi-immersive virtual environment. This project emphasizes two key components from the classical product design cycle: freeform modeling and analysis. In the freeform modeling stage, content creation in the form of two-handed sculpting of arbitrary objects using polygonal, volumetric or mathematically defined primitives is emphasized, whereas the analysis component provides the tools required for pre- and post-processing steps for finite element analysis tasks applied to the created models.

We present a multiresolution technique for interactive texture based rendering of arbitrarily oriented cutting planes for very large data sets. This method uses an adaptive scheme that renders the data along a cutting plane at different resolutions: higher resolution near the point-of-interest and lower resolution away from the point-of-interest. The algorithm is based on the segmentation of texture space into an octree, where the leaves of the tree define the original data and the internal nodes define lower-resolution versions. Rendering is done adaptively by selecting high-resolution cells close to a center of attention and low-resolution cells away from it. We limit the artifacts introduced by this method by blending between different levels of resolution to produce a smooth image. This technique can be used to produce viewpoint-dependent renderings.

Understanding turbulence and mix in compressible flows is of fundamental importance to real-world applications such as chemical combustion and supernova evolution. The ability to run in three dimensions and at very high resolution is required for the simulation to accurately represent the interaction of the various length scales, and consequently, the reactivity of the intermixin species. Toward this end, we have carried out a very high resolution (over 8 billion zones) 3-D simulation of the Richtmyer-Meshkov instability and turbulent mixing on the IBM Sustained Stewardship TeraOp (SST) system, developed under the auspices of the Department of Energy (DOE) Accelerated Strategic Computing Initiative (ASCI) and located at Lawrence Livermore National Laboratory. We have also undertaken an even higher resolution proof-of-principle calculation (over 24 billion zones) on 5832 processors of the IBM system, which executed for over an hour at a sustained rate of 1.05 Tflop/s, as well as a short calculation with a modified algorithm that achieved a sustained rate of 1.18Tflop/s. The full production scientific simulation, using a further modified algorithm, ran for 27,000 timesteps in slightly over a week of wall time using 3840 processors of the IBM system, clockin a sustained throughput of roughly 0.6 teraflop per second (32-bit arithmetic). Nearly 300,000 graphics files comprising over three terabytes of data were produced and post-processed. The capability of running in 3-D at high resolution enabled us to get a more accurate and detailed picture of the fluid-flow structure - in particular, to simulate the development of fine scale structures from the interactions of long-and short-wavelength phenomena, to elucidate differences between two-dimensional and three-dimensional turbulence, to explore a conjecture regarding the transition from unstable flow to fully developed turbulence with increasing Reynolds number, and to ascertain convergence of the computed solution with respect to mesh resolution.