Tech Briefs

Array-Pattern-Match Compiler for Opportunistic Data Analysis

A computer program has been written to facilitate real-time sifting of scientific data as they are acquired to find data patterns deemed to warrant further analysis. The patterns in question are of a type denoted array patterns, which are specified by nested parenthetical expressions. [One example of an array pattern is ((>3) 0 (≠1)): this pattern matches a vector of at least three elements, the first of which exceeds 3, the second of which is 0, and the third of which does not equal 1.] This program accepts a high-level description of a static array pattern and compiles a highly optimal and compact other program to determine whether any given instance of any data array matches that pattern. The compiler implemented by this program is independent of the target language, so that as new languages are used to write code that processes scientific data, they can easily be adapted to this compiler. This program runs on a variety of different computing platforms. It must be run in conjunction with any one of a number of Lisp compilers that are available commercially or as shareware.

Posted in: Briefs, TSP, Software, Analysis methodologies, Data acquisition and handling


Pre-Processor for Compression of Multispectral Image Data

A computer program that preprocesses multispectral image data has been developed to provide the Mars Exploration Rover (MER) mission with a means of exploiting the additional correlation present in such data without appreciably increasing the complexity of compressing the data. When used in conjunction with ICER, a previously developed image-data-compression program, this program enables improved compression of multispectral images, compared to that achievable by use of ICER alone. As such, it is a straightforward means of achieving much of the gain possible from exploiting spectral correlation. This preprocessor software accommodates up to seven images that are different spectral bands of the same scene. The software performs an approximate discrete cosine transform (DCT) pixelwise across the spectral bands. The software is written for speed; in particular the DCT operation performs only integer operations (producing integer output) and uses multiplications sparingly. Separate code is used for each possible number of spectral bands, including numbers for which fast DCT functions are not normally implemented. The DCT output is scaled so that, if the original images have a bit depth of at most 12, the transformed images are guaranteed to have a dynamic range appropriate for compression by the ICER software on the MER rovers. The resulting transformed bands are compressed individually by ICER. To reconstruct the images, the transformed images are first decompressed by use of the decompressor for ICER, then the resulting reconstructed images are passed to an inverse-DCT subprogram, which reconstructs the various spectral bands.

Posted in: Briefs, TSP, Software, Computer software and hardware, Imaging and visualization, Data management


Compressing Image Data While Limiting the Effects of Data Losses

ICER is computer software that can perform both lossless and lossy compression and decompression of gray-scaleimage data using discrete wavelet transforms. Designed for primary use in transmitting scientific image data from distant spacecraft to Earth, ICER incorporates an error-containment scheme that limits the adverse effects of loss of data and is well suited to the data packets transmitted by deep-space probes. The error-containment scheme includes utilization of the algorithm described in “Partitioning a Gridded Rectangle Into Smaller Rectangles” (NPO-30479), NASA Tech Briefs, Vol. 28, No. 7 (July 2004), page 56. ICER has performed well in onboard compression of thousands of images transmitted from the Mars Exploration Rovers.

Posted in: Briefs, TSP, Software, Imaging and visualization, Data management


Flight Operations Analysis Tool

Flight Operations Analysis Tool (FLOAT) is a computer program that partly automates the process of assessing the benefits of planning spacecraft missions to incorporate various combinations of launch vehicles and payloads (see figure). Designed primarily for use by an experienced systems engineer, FLOAT makes it possible to perform a preliminary analysis of trade-offs and costs of a proposed mission in days, whereas previously, such an analysis typically lasted months. FLOAT surveys a variety of prior missions by querying data from authoritative NASA sources pertaining to 20 to 30 mission and interface parameters that define space missions. FLOAT provides automated, flexible means for comparing the parameters to determine compatibility or the lack thereof among payloads, spacecraft, and launch vehicles, and for displaying the results of such comparisons. Sparseness, typical of the data available for analysis, does not confound this software. FLOAT effects an iterative process that identifies modifications of parameters that could render compatible an otherwise incompatible mission set.The Database Overview shows current and future capabilities.

Posted in: Briefs, TSP, Software, Computer software and hardware, Systems engineering, Launch vehicles


Improvement in Visual Target Tracking for a Mobile Robot

In an improvement of the visual-targettracking software used aboard a mobile robot (rover) of the type used to explore the Martian surface, an affine-matching algorithm has been replaced by a combination of a normalized-cross- correlation (NCC) algorithm and a template-image- magnification algorithm. Although neither NCC nor template-image magnification is new, the use of both of them to increase the degree of reliability with which features can be matched is new. In operation, a template image of a target is obtained from a previous rover position, then the magnification of the template image is based on the estimated change in the target distance from the previous rover position to the current rover position (see figure). For this purpose, the target distance at the previous rover position is determined by stereoscopy, while the target distance at the current rover position is calculated from an estimate of the current pose of the rover. The template image is then magnified by an amount corresponding to the estimated target distance to obtain a best template image to match with the image acquired at the current rover position.Turn-in-Place Experiments show beginning image (left) and end image (right) after 80° rover rotation. As the rover turns, the mast camera turns in the opposite direction to point to the target.

Posted in: Briefs, TSP, Software, Mathematical models, Imaging and visualization, Robotics


Software for Simulating Air Traffic

Future Air Traffic Management Concepts Evaluation Tool (FACET) is a system of software for performing computational simulations for evaluating advanced concepts of advanced air-traffic management. FACET includes a program that generates a graphical user interface plus programs and databases that implement computational models of weather, airspace, airports, navigation aids, aircraft performance, and aircraft trajectories. Examples of concepts studied by use of FACET include aircraft self-separation for free flight; prediction of air-traffic-controller workload; decision support for direct routing; integration of spacecraftlaunch operations into the U.S. national airspace system; and traffic-flow-management using rerouting, metering, and ground delays. Aircraft can be modeled as flying along either flight-plan routes or great-circle routes as they climb, cruise, and descend according to their individual performance models. The FACET software is modular and is written in the Java and C programming languages. The architecture of FACET strikes a balance between flexibility and fidelity; as a consequence, FACET can be used to model system- wide airspace operations over the contiguous U.S., involving as many as 10,000 aircraft, all on a single desktop or laptop computer running any of a variety of operating systems. Two notable applications of FACET include: (1) reroute conformance monitoring algorithms that have been implemented in one of the Federal Aviation Administration’s nationally deployed, real-time, operational systems; and (2) the licensing and integration of FACET with the commercially available Flight Explorer, which is an Internetbased, real-time flight-tracking system.

Posted in: Briefs, TSP, Software, Simulation and modeling, Computer software and hardware, Air traffic control


Automated Vectorization of Decision-Based Algorithms

Virtually all existing vectorization algorithms are designed to only analyze the numeric properties of an algorithm and distribute those elements across multiple processors. This advances the state of the practice because it is the only known system, at the time of this reporting, that takes high-level statements and analyzes them for their decision properties and converts them to a form that allows them to automatically be executed in parallel. The software takes a high-level source program that describes a complex decision-based condition and rewrites it as a disjunctive set of component Boolean relations that can then be executed in parallel. This is important because parallel architectures are becoming more commonplace in conventional systems and they have always been present in NASA flight systems. This technology allows one to take existing condition-based code and automatically vectorize it so it naturally decomposes across parallel architectures.

Posted in: Briefs, TSP, Software, Mathematical models, Architecture, Computer software and hardware, Performance upgrades


The U.S. Government does not endorse any commercial product, process, or activity identified on this web site.