Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Contour tree”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 19 records
All sourcesNASA NTRSDOE OSTI
DOE OSTI2022

Distributed Hierarchical Contour Trees

Contour trees are a significant tool for data analysis as they capture both local and global variation. However, their utility has been limited by scalability, in particular for distributed computation and storage. We report a distributed data structure for storing the contour tree of a data set distributed on a cluster, based on a fan-in hierarchy, and an algorithm for computing it based on the boundary tree that represents only the superarcs of a contour tree that involve contours that cross boundaries between blocks. This allows us to limit the communication cost for contour tree computation to the complexity of the block boundaries rather than of the entire data set.

Carr, Hamish A↗
DOE OSTI2021

Optimization and Augmentation for Data Parallel Contour Trees

Contour trees are used for topological data analysis in scientific visualization. While originally computed with serial algorithms, recent work has introduced a vector-parallel algorithm. Furthermore, this algorithm is relatively slow for fully augmented contour trees which are needed for many practical data analysis tasks. We therefore introduce a representation called the hyperstructure that enables efficient searches through the contour tree and use it to construct a fully augmented contour tree in data parallel, with performance on average 6 times faster than the state-of-the-art parallel algorithm in the TTK topological toolkit.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2024

Distributed Augmentation, Hypersweeps, and Branch Decomposition of Contour Trees for Scientific Exploration

Contour trees describe the topology of level sets in scalar fields and are widely used in topological data analysis and visualization. A main challenge of utilizing contour trees for large-scale scientific data is their computation at scale using highperformance computing. To address this challenge, recent work has introduced distributed hierarchical contour trees for distributed computation and storage of contour trees. However, effective use of these distributed structures in analysis and visualization requires subsequent computation of geometric properties and branch decomposition to support contour extraction and exploration. In this work, we introduce distributed algorithms for augmentation, hypersweeps, and branch decomposition that enable parallel computation of geometric properties, and support the use of distributed contour trees as query structures for scientific exploration. Finally, we evaluate the parallel performance of these algorithms and apply them to identify and extract important contours for scientific visualization.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2025

Extremely Scalable Distributed Computation of Contour Trees via Pre-Simplification

Contour trees offer an abstract representation of the level set topology in scalar fields and are widely used in topological data analysis and visualization. However, applying contour trees to large-scale scientific datasets remains challenging due to scalability limitations. Recent developments in distributed hierarchical contour trees have addressed these challenges by enabling scalable computation across distributed systems. Building on these structures, advanced analytical tasks—such as volumetric branch decomposition and contour extraction—have been introduced to facilitate large-scale scientific analysis. Despite these advancements, such analytical tasks substantially increase memory usage, which hampers scalability. In this paper, we propose a pre-simplification strategy to significantly reduce the memory overhead associated with analytical tasks on distributed hierarchical contour trees. We demonstrate enhanced scalability through strong scaling experiments, constructing the largest known contour tree—comprising over half a trillion nodes with complex topology—in under 15 minutes on a dataset containing 550 billion elements.

Li, Mingzhe [University of Utah]↗
DOE OSTI2022

A Mountaintop View Requires Minimal Sorting: A Faster Contour Tree Algorithm

Consider a scalar field f : M → R, where M is a triangulated simplicial mesh in R d . A level set, or contour, at value v is a connected component of f –1 (v). As v is changed, these contours change topology, merge into each other, or split. Contour trees are concise representations of f that track this contour behavior. The vertices of these trees are the critical points of f, where the gradient is zero. The edges represent changes in the topology of contours. It is a fundamental data structure in data analysis and visualization, and there is significant previous work (both theoretical and practical) on algorithms for constructing contour trees. Suppose M has n vertices, N facets, and t critical points. A classic result of Carr, Snoeyink, and Axen (2000) gives an algorithm that takes O(n log n+Nα(N)) time (where α(·) is the inverse Ackermann function). A further improvement to O(t log t + N) time was given by Chiang et al. All these algorithms involve a global sort of the critical points, a significant computational bottleneck. Unfortunately, lower bounds of Ω(t log t) also exist. We present the first algorithm that can avoid the global sort and has a refined time complexity that depends on the contour tree structure. Intuitively, if the tree is short and fat, we get significant improvements in running time. For a partition of the contour tree into a set of descending paths, P, our algorithm runs in O($\Sigma$ pϵP |p| log |p| + tα(t) + N). This is at most O(t log D + N), where D is the diameter of the contour tree. Moreover, it is O(tα(t) + N) for balanced trees, a significant improvement over the previous complexity. Our algorithm requires numerous ideas: partitioning the contour tree into join and split trees, a local growing procedure to iteratively build contour trees, and the use of heavy path decompositions for the time complexity analysis. There is a crucial use of a family of binomial heaps to maintain priorities, ensuring that any comparison made is between comparable nodes of the contour tree. We also prove lower bounds showing that the $\Sigma$ pϵP |p| log |p| complexity is inherent to computing contour trees.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

Scalar Field Comparison with Topological Descriptors: Properties and Applications for Scientific Visualization

In topological data analysis and visualization, topological descriptors such as persistence diagrams, merge trees, contour trees, Reeb graphs, and Morse–Smale complexes play an essential role in capturing the shape of scalar field data. Herein we present a state–of–the–art report on scalar field comparison using topological descriptors. We provide a taxonomy of existing approaches based on visualization tasks associated with three categories of data: single fields, time–varying fields, and ensembles. These tasks include symmetry detection, periodicity detection, key event/feature detection, feature tracking, clustering, and structure statistics. Our main contributions include the formulation of a set of desirable mathematical and computational properties of comparative measures, and the classification of visualization tasks and applications that are enabled by these measures.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS1993

Entropy reduction via simplified image contourization

The process of contourization is presented which converts a raster image into a set of plateaux or contours. These contours can be grouped into a hierarchical structure, defining total spatial inclusion, called a contour tree. A contour coder has been developed which fully describes these contours in a compact and efficient manner and is the basis for an image compression method. Simplification of the contour tree has been undertaken by merging contour tree nodes thus lowering the contour tree's entropy. This can be exploited by the contour coder to increase the image compression ratio. By applying general and simple rules derived from physiological experiments on the human vision system, lossy image compression can be achieved which minimizes noticeable artifacts in the simplified image.

Turner, Martin J.↗
DOE OSTI2023

TopoSZ: Preserving Topology in Error-Bounded Lossy Compression

Existing error-bounded lossy compression techniques control the pointwise error during compression to guarantee the integrity of the decompressed data. However, they typically do not explicitly preserve the topological features in data. When performing post hoc analysis with decompressed data using topological methods, preserving topology in the compression process to obtain topologically consistent and correct scientific insights is desirable. In this paper, we introduce TopoSZ, an error-bounded lossy compression method that preserves the topological features in 2D and 3D scalar fields. Specifically, we aim to preserve the types and locations of local extrema as well as the level set relations among critical points captured by contour trees in the decompressed data. The main idea is to derive topological constraints from contour-tree-induced segmentation from the data domain, and incorporate such constraints with a customized error-controlled quantization strategy from the SZ compressor (version 1.4). In conclusion, our method allows users to control the pointwise error and the loss of topological features during the compression process with a global error bound and a persistence threshold.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2024

Lorentzian contours for tree-level string amplitudes

We engineer compact contours on the moduli spaces of genus-zero Riemann surfaces that achieve analytic continuation from Euclidean to Lorentzian worldsheets. These generalized Pochhammer contours are based on the combinatorics of associahedra and make the analytic properties of tree-level amplitudes entirely manifest for any number and type of external strings. We use them in practice to perform first numerical computations of open and closed string amplitudes directly in the physical kinematics for n=4,5,6,7,8,9 n = 4 , 5 , 6 , 7 , 8 , 9 . We provide a code that allows anyone to do such computations.

Physics↗
NASA NTRS1972

Post-analysis report on Chesapeake Bay data processing

The additional processing performed on data collected over the Rhode River Test Site and Forestry Site in November 1970 is reported. The techniques and procedures used to obtain the processed results are described. Thermal data collected over three approximately parallel lines of the site were contoured, and the results color coded, for the purpose of delineating important scene constituents and to identify trees attacked by pine bark beetles. Contouring work and histogram preparation are reviewed and the important conclusions from the spectral analysis and recognition computer (SPARC) signature extension work are summarized. The SPARC setup and processing records are presented and recommendations are made for future data collection over the site.

Thomson, F.↗
NASA NTRS1972

Thermal contouring of forestry data: Wallops Island

The contouring of 8-13.5 micrometer thermal data collected over a forestry site in Virginia is described. The data were collected at an altitude of 1000 ft above terrain on November 4, 1970. The site was covered on three approximately parallel lines. The purpose of the contouring was to attempt to delineate pine trees attacked by southern pine bark beetle, and to map other important terrain categories. Special processing steps were required to achieve the correct aspect ratio of the thermal data. The reference for the correction procedure was color infrared photography. Data form and quality are given, processing steps are outlined, a brief interpretation of results is given, and conclusion are presented.

Thomson, F.↗
NASA NTRS1991

Data analysis using scale-space filtering and Bayesian probabilistic reasoning

This paper describes a program for analysis of output curves from Differential Thermal Analyzer (DTA). The program first extracts probabilistic qualitative features from a DTA curve of a soil sample, and then uses Bayesian probabilistic reasoning to infer the mineral in the soil. The qualifier module employs a simple and efficient extension of scale-space filtering suitable for handling DTA data. We have observed that points can vanish from contours in the scale-space image when filtering operations are not highly accurate. To handle the problem of vanishing points, perceptual organizations heuristics are used to group the points into lines. Next, these lines are grouped into contours by using additional heuristics. Probabilities are associated with these contours using domain-specific correlations. A Bayes tree classifier processes probabilistic features to infer the presence of different minerals in the soil. Experiments show that the algorithm that uses domain-specific correlation to infer qualitative features outperforms a domain-independent algorithm that does not.

Kulkarni, Deepak↗
DOE OSTI2025

Cuts and contours

The traditional formulation of string amplitudes via worldsheet integrals provides a parametrization of the moduli space that fails to expose the complete singularity structure of the amplitudes. This problem is solved by the positive parametrization of string amplitudes given by surfaceology. In this work, we use this formalism to study a number of properties of string amplitudes at tree-level and one-loop. We introduce several global prescriptions for an integration contour for which the integrals are finite everywhere in kinematic space. At tree-level, this is done in two ways: one directly implements the Feynman iε to analytically continue from Euclidean to Lorentzian worldsheets; the other is a generalization of the closed Pochhammer contour to arbitrary number of points. At loop-level, we present a systematic way of extracting cuts directly from the worldsheet integrand. This provides a powerful set of unitarity constraints, which we use to test the consistency of different “stringy” UV regularizations of field theory amplitudes. In addition, we identify the massive threshold expansion of the integrand, which allows us to reduce the problem to a finite set of Feynman integrals in Schwinger parametrization and provide a straightforward contour prescription reminiscent of its field-theory version.

Bosonic Strings↗
NASA NTRS1970

The use of multispectral sensing techniques to detect ponderosa pines trees under stress from insects or diseases

The detection of stress induced by bark beetles in conifers is reviewed in two sections: (1) the analysis of very small scale aerial photographs taken by NASA's RB-57F aircraft on August 10, 1969, and (2) the analysis of multispectral imagery obtained by the optical-mechanical line scanner. Underexposure of all films taken from the RB-57 aircraft and inadequate flight coverage prevented drawing definitive conclusions regarding optimum scales and film combinations to detect the discolored infestations. Preprocessing of the scanner signals by both analog and digital computers improved the accuracy of target recognition. Selection and ranking of the best channels for signature recognition was the greatest contribution of digital processing. Improvements were made in separating hardwoods from conifers and old-kill pine trees from recent discolored trees and from healthy trees, but accuracy of detecting the green infested trees is still not acceptable on either the SPARC or thermal-contouring processor. From six years of experience in processing line scan data it is clear that the greatest gain in previsual detection of stress will occur when registered multispectral data from a single aperture or common instantaneous field of view scanner system can be collected and processed.

Heller, R. C.↗
DOE OSTI2025

Smooth splitting and zeros from on-shell recursion

We describe a new approach to understanding the origins of recently discovered “hidden zeros” and “smooth splitting” of tree-level amplitudes in Tr ϕ 3 , Non-Linear Sigma Model (NLSM), Yang-Mill-Scalar (YMS) and the special Galileon. Introducing a new type of linear shift in kinematic space we demonstrate that the mysterious splitting formulae follow from a simple contour integration argument in the style of on-shell recursion. The argument makes use of only standard notions of tree-level factorization on propagators, but assumes improved UV behavior in the form of the absence of a residue at infinity. In the case of Tr ϕ 3 and NLSM this is proven by identifying our shift as a special case of a more general construction called a g-vector shift; in the case of YMS it remains an unproven conjecture. This recursive perspective leads to numerous new results: we derive generalizations of the splitting formulae on more relaxed near-zero kinematics, including interesting new kinematic limits in which the amplitude splits into a triple-product; we also demonstrate that the uncolored special Galileon model has improved UV scaling and hence also splits. We also investigate the possible realization of hidden zeros in four dimensions. The conditions under which the dimensionality constraints are compatible with zero kinematics is investigated in detail for Tr ϕ 3 and YMS; for the latter we find they can be realized only with certain restrictions on external helicity states. The realizable 4d zeros are proven by a similar recursive argument based on BCFW and is found to generalize to a new class of intrinsically 4d “helicity zeros” present in all sectors of YM and also gravity.

effective field theories↗
DOE OSTI2020

Scattering equations in AdS: scalar correlators in arbitrary dimensions

We introduce a bosonic ambitwistor string theory in AdS space. Even though the theory is anomalous at the quantum level, one can nevertheless use it in the classical limit to derive a novel formula for correlation functions of boundary CFT operators in arbitrary space-time dimensions. The resulting construction can be treated as a natural extension of the CHY formalism for the flat-space S-matrix, as it similarly expresses tree-level amplitudes in AdS as integrals over the moduli space of Riemann spheres with punctures. These integrals localize on an operator-valued version of scattering equations, which we derive directly from the ambitwistor string action on a coset manifold. As a testing ground for this formalism we focus on the simplest case of ambitwistor string coupled to two cur- rent algebras, which gives bi-adjoint scalar correlators in AdS. In order to evaluate them directly, we make use of a series of contour deformations on the moduli space of punctured Riemann spheres and check that the result agrees with tree level Witten diagram computations to all multiplicity. We also initiate the study of eigenfunctions of scattering equations in AdS, which interpolate between conformal partial waves in different OPE channels, and point out a connection to an elliptic deformation of the Calogero-Sutherland model.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗
NASA NTRS1989

Advances in image compression and automatic target recognition; Proceedings of the Meeting, Orlando, FL, Mar. 30, 31, 1989

Various papers on image compression and automatic target recognition are presented. Individual topics addressed include: target cluster detection in cluttered SAR imagery, model-based target recognition using laser radar imagery, Smart Sensor front-end processor for feature extraction of images, object attitude estimation and tracking from a single video sensor, symmetry detection in human vision, analysis of high resolution aerial images for object detection, obscured object recognition for an ATR application, neural networks for adaptive shape tracking, statistical mechanics and pattern recognition, detection of cylinders in aerial range images, moving object tracking using local windows, new transform method for image data compression, quad-tree product vector quantization of images, predictive trellis encoding of imagery, reduced generalized chain code for contour description, compact architecture for a real-time vision system, use of human visibility functions in segmentation coding, color texture analysis and synthesis using Gibbs random fields.

Tescher, Andrew G.↗
NASA NTRS1990

Computer vision techniques for rotorcraft low altitude flight

Rotorcraft operating in high-threat environments fly close to the earth's surface to utilize surrounding terrain, vegetation, or manmade objects to minimize the risk of being detected by an enemy. Increasing levels of concealment are achieved by adopting different tactics during low-altitude flight. Rotorcraft employ three tactics during low-altitude flight: low-level, contour, and nap-of-the-earth (NOE). The key feature distinguishing the NOE mode from the other two modes is that the whole rotorcraft, including the main rotor, is below tree-top whenever possible. This leads to the use of lateral maneuvers for avoiding obstacles, which in fact constitutes the means for concealment. The piloting of the rotorcraft is at best a very demanding task and the pilot will need help from onboard automation tools in order to devote more time to mission-related activities. The development of an automation tool which has the potential to detect obstacles in the rotorcraft flight path, warn the crew, and interact with the guidance system to avoid detected obstacles, presents challenging problems. Research is described which applies techniques from computer vision to automation of rotorcraft navigtion. The effort emphasizes the development of a methodology for detecting the ranges to obstacles in the region of interest based on the maximum utilization of passive sensors. The range map derived from the obstacle-detection approach can be used as obstacle data for the obstacle avoidance in an automatic guidance system and as advisory display to the pilot. The lack of suitable flight imagery data presents a problem in the verification of concepts for obstacle detection. This problem is being addressed by the development of an adequate flight database and by preprocessing of currently available flight imagery. The presentation concludes with some comments on future work and how research in this area relates to the guidance of other autonomous vehicles.

Sridhar, Banavar↗