ALBERT

Description: Within the NASA Intelligent Systems Program, the Intelligent Data Understanding (IDU) element develops techniques for transforming data into scientific understanding. Automating such tools is critical for space science, space-based earth science, and planetary exploration with onboard scientific data analysis. Intelligent data understanding (IDU) is about extracting meaning from large, diverse science and engineering databases, via autonomous techniques that transform very large datasets into understanding. The earth science community in particular needs new tools for analyzing multi-formatted and geographically distributed datasets and for identifying cause-effect relationships in the complex data. Research within the IDU program element seeks to automate data analysis tasks so that humans can focus on creative hypothesis generation and knowledge synthesis. It may also enable NASA space missions in which autonomous agents must generate knowledge and take actions, and missions where limited bandwidth permits transmission of only the most interesting scientific observations, summaries, and conclusions. Twenty-seven research projects are-currently funded.

Description: A hierarchical set of image segmentations is a set of several image segmentations of the same image at different levels of detail in which the segmentations at coarser levels of detail can be produced from simple merges of regions at finer levels of detail. In [1], Tilton, et a1 describes an approach for producing hierarchical segmentations (called HSEG) and gave a progress report on exploiting these hierarchical segmentations for image information mining. The HSEG algorithm is a hybrid of region growing and constrained spectral clustering that produces a hierarchical set of image segmentations based on detected convergence points. In the main, HSEG employs the hierarchical stepwise optimization (HSWO) approach to region growing, which was described as early as 1989 by Beaulieu and Goldberg. The HSWO approach seeks to produce segmentations that are more optimized than those produced by more classic approaches to region growing (e.g. Horowitz and T. Pavlidis, [3]). In addition, HSEG optionally interjects between HSWO region growing iterations, merges between spatially non-adjacent regions (i.e., spectrally based merging or clustering) constrained by a threshold derived from the previous HSWO region growing iteration. While the addition of constrained spectral clustering improves the utility of the segmentation results, especially for larger images, it also significantly increases HSEG s computational requirements. To counteract this, a computationally efficient recursive, divide-and-conquer, implementation of HSEG (RHSEG) was devised, which includes special code to avoid processing artifacts caused by RHSEG s recursive subdivision of the image data. The recursive nature of RHSEG makes for a straightforward parallel implementation. This paper describes the HSEG algorithm, its recursive formulation (referred to as RHSEG), and the implementation of RHSEG using massively parallel GNU-LINUX software. Results with Landsat TM data are included comparing RHSEG with classic region growing.

Description: A modification to increase processing speed has been made in the algorithm and implementing software reported in Modified Recursive Hierarchical Segmentation of Data (GSC-14681-1), NASA Tech Briefs, Vol. 30, No. 6 (June 2006), page 51. That software performs recursive hierarchical segmentation of data having spatial characteristics (e.g., spectral-image data). The segmentation process includes an iterative subprocess, in each iteration of which it is necessary to determine a best pair of regions to merge [merges being justified by one or more measure(s) similarity of pixels in the regions]. In the previously reported version of the algorithm and software, the choice of a best pair of regions to merge involved the use of a fully sorted list of regions. That version was computationally inefficient because a fully sorted list is not needed: what is needed is only the identity of the pair of regions characterized by the smallest measure of dissimilarity. The present modification replaces the use of a fully sorted list with the use of data heaps, which are computationally more efficient for performing the required comparisons among dissimilarity measures. The modification includes the incorporation of standard and modified functions for creating and updating data heaps

Description: A further modification has been made in the algorithm and implementing software reported in Modified Recursive Hierarchical Segmentation of Data (GSC- 14681-1), NASA Tech Briefs, Vol. 30, No. 6 (June 2006), page 51. That software performs recursive hierarchical segmentation of data having spatial characteristics (e.g., spectral-image data). The output of a prior version of the software contained artifacts, including spurious segmentation-image regions bounded by processing-window edges. The modification for suppressing the artifacts, mentioned in the cited article, was addition of a subroutine that analyzes data in the vicinities of seams to find pairs of regions that tend to lie adjacent to each other on opposite sides of the seams. Within each such pair, pixels in one region that are more similar to pixels in the other region are reassigned to the other region. The present modification provides for a parameter ranging from 0 to 1 for controlling the relative priority of merges between spatially adjacent and spatially non-adjacent regions. At 1, spatially-adjacent-/spatially- non-adjacent-region merges have equal priority. At 0, only spatially-adjacent-region merges (no spectral clustering) are allowed. Between 0 and 1, spatially-adjacent- region merges have priority over spatially- non-adjacent ones.

Description: The Hierarchical Segmentation (HSEG) algorithm is an approach for producing high quality, hierarchically related image segmentations. The VisiMine image information mining system utilizes clustering and segmentation algorithms for reducing visual information in multispectral images to a manageable size. The project discussed herein seeks to enhance the VisiMine system through incorporating hierarchical segmentations from HSEG into the VisiMine system.