| Skip to content | |||||
 |
|
||||
 |
|||||
 |
|
||||
Featured Technologies  |
 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
For faster, highly accurate analysis of single band, multispectral, or hyperspectral imagery data at resolutions up to 8000x8000 pixels
Developed by NASA Goddard Space Flight Center’s Dr. James C. Tilton, the Recursive Hierarchical Segmentation (RHSEG) Pre-processing Software provides hierarchical segmentation (pre-processing) of image and image-like data. The RHSEG Pre-processing Software significantly improves the extraction of patterns from complex data sets. Optimized for speed and accuracy, this patent-pending algorithm provides the user with precise control for selecting the desired level of detail from the hierarchy of results. The software allows the user to group non-spatially adjacent regions for unprecedented accuracy and flexibility with a wide range of image and data types. Originally designed for remote earth sensing, the RHSEG Pre-processing Software is broadly applicable to a range of applications, from medical imaging to data mining and is now capable of three-dimensional data analysis. The software technology is available for license in two versions. The Artifact Elimination Version (RHSEG-AE) includes the publicly available Core RHSEG Pre-processing Software, the patent-pending Artifact Elimination technology, and the publicly available HSEGViewer. The Enhanced Performance Version (RHSEG-AEP) includes the Core RHSEG Pre-processing Software, the patent-pending Artifact Elimination technology, the patent-pending Parallel Processing technology, and the HSEGViewer. Both versions are available for licensing. GSFC seeks to license the RHSEG technologies to private industry for use in commercial applications. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
The RHSEG Pre-processing Software and HSEGViewer produce a number of benefits. These include the following:
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
The RHSEG Pre-processing Software is useful for pre-processing image and image-like data for further intelligent analysis. Possible applications include, but are not limited to:
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
NASA has prepared an evaluation version of the image processing software called RHSEG-AED that is useful for demonstrating the capabilities of the Artifact Elimination Version. It is available for Windows and Unix/Solaris platforms and is designed for use on a single processor. In addition to RHSEG-AE, for improved performance segmenting larger images, the Enhanced Performance Version (RHSEG-AEP) is available for license for use on clusters of processors. (There is no demo available for the Enhanced Performance Version.) RHSEG-AED is the demo version of GSFC’s licensable RHSEG-AE software, consisting of the Core RHSEG Pre-processing Software, Artifact Elimination technology, and the HSEGViewer. It is available for a free, 90-day trial, compiled for Windows and Unix/Solaris platforms. System requirements are as follows: PC with 1 GHz processor and 128 MB RAM. If you would like to receive free, 90-day evaluation software, please go to Register Your Interest and fill out the required form, indicating which platform you need. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
+ What It Is The Recursive Hierarchical Segmentation (RHSEG) Pre-processing Software is an approach for partitioning two- and/or three-dimensional image or image-like data into regions or clusters at various levels of detail. Using this approach, regions of data at coarser levels of detail are hierarchically related to regions of data at finer levels of detail. Following processing by the software, data are grouped and can be analyzed in terms of hierarchically related regions, rather than as individual data points, enabling a more consistent and accurate analysis. To understand the richness of the RHSEG Pre-processing Software’s capabilities, it is helpful to have some background on image segmentation in general.
Image segmentation is the partitioning of an image into related sections or regions. Most approaches to image segmentation fall into one of three categories: characteristic feature thresholding or clustering, boundary detection, or region growing, each of which has advantages and disadvantages. One type of region growing approach is called "hierarchical step-wise optimization" (HSWO). The core hierarchical segmentation software (HSEG) approach is a hybrid of HSWO region growing and spectral clustering. It differs from HSWO in that HSEG optionally alternates spectral clustering iterations with region growing iterations (the region growing iterations merge spatially adjacent regions, while the spectral clustering iterations merge non-spatially adjacent regions). HSEG is unique in that it enables the production of a segmentation hierarchy by allowing options for different dissimilarity criteria and by detecting and recording results from iterations where natural convergences are found. A hierarchical set of image segmentations is a set of image segmentations conducted at different levels of detail in which the less detailed segmentations can be produced from specific merges of regions contained in the more detailed segmentations. Unlike most other segmentation approaches that produce a single segmentation result, a natural product of the HSEG approach is a hierarchical set of segmentations selected by noting significant changes in the merging threshold. A single segmentation can be selected out of the segmentation hierarchy by examining how the features of individual regions change throughout each level of detail.
Dr. Tilton began developing the hierarchical segmentation technology in 1983, having become familiar with earth sciences and remote sensing while in graduate school. During his initial years at NASA he began to think about image segmentation and analyzing the data beyond the typical "per-pixel" approach, since each pixel does not necessarily provide enough information about where it fits into the overall "scene." Dr. Tilton theorized that a better understanding could be achieved by considering the context of the image and looking at the objects in the image rather than the individual pixels. It was that theory that ultimately led to the initial version of the core HSEG software algorithm, a hybrid of HSWO region growing and spectral clustering. HSEG optionally alternates spectral clustering iterations with region growing iterations; the region growing iterations merge spatially adjacent regions, while the spectral clustering iterations merge non-spatially adjacent regions. Recursive Formulation Because the introduction of alternating iterations of spectral clustering along with region growing in the HSEG algorithm significantly increased computational demands, a recursive formulation of HSEG (RHSEG) was developed. The RHSEG approach is a divide-and-conquer, recursive implementation of HSEG. RHSEG not only limits the number of comparisons between non-spatially adjacent regions to a more reasonable number, it also lends itself to a straightforward and efficient implementation on parallel (rather than serial) computing platforms. The implementation of RHSEG on parallel computing platforms (Enhanced Performance Version) is very effective in exploiting available concurrent processing, making it possible to process very large images in a reasonable amount of processing time (e.g., less than 10 minutes for a full Landsat TM scene). Data Swapping Scheme (for single processor platforms) For those without access to parallel processing machines, the newest version RHSEG uses a newly implemented data swapping scheme to enable processing of larger image sets on single processor platforms. For example, a 6912-column, 6528-row, 6-band Landsat TM image can be processed in 8 hours, whereas previous versions were unable to process images of this magnitude. The parallel version is still significantly faster, processing the same image in only 1.5 minutes. Artifact Elimination Version Also available with the RHSEG Pre-processing Software is a special version (Artifact Elimination Version) that avoids processing window artifacts caused by the RHSEG Pre-processing Software’s recursive subdivision and subsequent combination of the image data. HSEGViewer The output of the RHSEG Pre-processing Software is a set of hierarchical segmentations. Most scientists, however, want a single segmentation to work with, rather than a set of segmentations. The problem, then, is selecting the appropriate image segmentation from the hierarchical set. At times this selection might be as simple as determining which single segmentation out of the hierarchical set is suitable for the application. Frequently, however, a single segmentation synthesized by combining segmentations from a number of the hierarchical segmentations would be more suitable. An additional program, HSEGViewer, has been developed to facilitate combining segmentations from a number of the hierarchical segmentations into a single segmentation. This tool enables the user to view the RHSEG Pre-processing Software output, facilitating the selection of segmentation sets. Non-Image Data RHSEG can also process non-image data as long as it has image-like characteristics when plotted on a one-, two-, or three-dimensional array. Data has image-like characteristics when data points that are positioned nearer to each other in an array are more highly correlated than data positioned further away. Three-dimensional Data (NEW!) The latest release of the RHSEG program includes the ability to analyze three-dimensional data. Because processing three-dimensional data increases computational demands, separate two-dimensional and three-dimensional versions are now available: rhseg_2d and rhseg_3d. Due to patent coverage restrictions, rhseg_3d is available to US entities only. Other New Developments Additional dissimilarity criteria are included in the latest release of the RHSEG program, including a criterion based on minimizing the change in image entropy, and three criteria developed for the analysis of hyperspectral data: the Spectral Angle Mapper (SAM), the Spectral Information Divergence (SID), and the Normalized Vector Distance.
The software begins with an initial partitioning of the image data (by default, each image pixel is placed into a separate partition or region) and then compares each region with spatially adjacent regions. Pairs of spatially adjacent regions that are most similar are then combined to form larger regions. Then, at the user’s option, pairs of non-spatially adjacent regions are compared and pairs of non-spatially adjacent regions that are at least as similar as the previously compared spatially adjacent regions are combined. This process continues until a prespecified minimum number of regions is reached (depending on the coarseness or fineness of detail desired). At this point, the process continues, but the segmentation results are monitored for significant changes between each iteration. These significant changes are detected by noting when the region maximum of the ratio between the dissimilarity of the region mean and the original image data for the current and previous iterations exceeds a specified threshold. If a significant change is detected, the segmentation results are saved prior to the significant change. Otherwise, the algorithm just continues to the next iteration. This comparison process continues until a two-region segmentation is reached. The saved segmentation results form the segmentation hierarchy output. That the RHSEG Pre-processing Software produces a hierarchical set of segmentations is a noteworthy and useful result, as illustrated in the following examples:
Example 1 (Choosing the number of larger regions to match analysis needs) Using the greatest number of regions (i.e., focusing on the finest level of detail available) is not always the ideal. Often, data trends are lost when viewing the data at their finest level (maximum number of regions), i.e., "not seeing the forest for the trees." That is why the program provides several levels of segmentation resolution to choose from. Below are samples of a segmented image as viewed using a different number of regions: Figure 1: These images show an example of segmentation detail varying with hierarchical level. The final example (f) shows the selection of image segments from different hierarchical levels, creating a segmentation result with a minimum number of regions that still delineates most of the segmentation detail of the most detailed level of the segmentation hierarchy. Figure 1(a) shows the original Landsat Thematic Mapper (TM) image shot from over central Washington, DC. Figure 1(b) shows a color-coded representation of the 7-region level of the segmentation hierarchy. There is a large background region (orange), along with a water region (dark blue), a water mix region that includes dark road features and bridges (light blue), a light colored roof region (light yellow), a bright roof region (white), and two other small, not clearly identifiable regions. Figure 1(c) shows a color-coded representation of the 12-region level of the segmentation hierarchy for the same image. The additional regions delineated at this hierarchical level include a large number of buildings (bright yellow), the Washington, DC mall area and other similar grassy areas (light green), thick vegetation (dark green), plus a couple of other small regions. Figure 1(d) shows a color-coded representation of the 25-region level of the segmentation hierarchy for the same image. Here the major areas of vegetation (green) are separated from the background area, which now is a mixed urban region (orange). In addition, some dark roads or parking areas are separated (dark red); there is some additional minor differentiation among building regions; and a number of other minor regions are differentiated. Figure 1(e) shows a color-coded representation of the 50-region level of the segmentation hierarchy for the same image. The most important additional regions delineated at this level are the road network (red) and regions that further differentiate between types of vegetation (shades of green). Although Figure 1(e) shows the most detail, it is not the best choice for identifying all trends, patterns, or features of the data. While it is necessary to use the 50-region level of the segmentation hierarchy to separate out the road network and differentiate between types of vegetation, other image areas are segmented in much more detail than is necessary. Figure 1(f) shows a selection of only 11 regions out of the segmentation hierarchy that represent all of the important regions in the image. These regions are water (blue), vegetation/light residential mix (medium green), the road network (red), very bright roofs (white), light colored roofs (light yellow), shallow water/water mix/bridges (light blue), grasses/mall (light green), a unique unidentified vegetation class (pink), a general urban area (orange), an apparent construction area (brown), and wooded areas (dark green). Example 2 (Enabling the grouping of non-spatially adjacent regions)
The RHSEG Pre-processing Software and HSEGViewer software algorithms have been tested and compared for typical image segmentation approaches. They have been successfully implemented by NASA for data mining and remote earth sensing image analysis within NASA Goddard Space Flight Center’s Intelligent Systems Group. They have also been used by NASA for analyzing frequency-versus-time data from the Imager for Magnetopause-to-Aurora Global Exploration (IMAGE) satellite and extracting key information from the data. Processing times for running the software on a single processor and on multiple processors using the Enhanced Performance Version have been compared. The processing time for RHSEG depends mainly on the data being processed, the number of levels of recursion employed (rnb_levels), and the value of the spclust_wght parameter. RHSEG utilizes the parameter spclust_wght to control the relative importance of merges between spatially adjacent regions and merges between non-spatially adjacent regions. When spclust_wght = 0.0, only merges between spatially adjacent regions are allowed. When spclust_wght = 1.0, merges between spatially adjacent and non-spatially adjacent regions are given equally priority. For values of spclust_wght between 0.0 and 1.0, spatially adjacent merges are given priority over non-spatially adjacent merges by a factor of 1.0/spclust_wght. The table below shows a comparison of some processing times (minutes:seconds) for 2.4 GHz processors with 1 GByte of RAM, on a six-band Landsat Thematic Mapper data set. The results demonstrate the effect of the rnb_levels and spclust_wght parameters on processing time. For spclust_wght = 0.0, processing times of less than 2 minutes are found with rnb_levels = 1 (i.e., no recursion) for images as large as 1024x1024. In this case, processing times are limited only by memory restraints. For spclust_wght > 0.0, recursion is required to obtain processing times of less than one hour for all but the smallest image sizes. Here processing times of under one hour are found for images as large as 1024x1024 with just one CPU using the program default value for rnb_levels. For images larger than 1024x1024, parallel processing is generally required for reasonable processing times. Images as large as about 7000x7000 can be processed in well under 10 minutes using 256 CPUs.
* Default value for this image size. † With init_threshold = 0.50. The technology has also been nonexclusively licensed to Bartron Medical Imaging, LLC. Bartron has launched a product for use in medical imaging (Med-Seg™) based on the NASA technology. Bartron has reported that the RHSEG Pre-processing Software enabled the company to successfully analyze and extract meaningful and significant features from grayscale data that was previously indistinguishable by the human eye.
Subdue’ing RHSEG: The Marriage of Graph-Based Knowledge Discovery (Subdue) with Image Segmentation Hierarchies (from RHSEG) for Data Analysis, Data Mining, and Knowledge Discovery RHSEG is a key technology in a NASA research project funded for fiscal year 2008 (Oct. 2007 through Sept. 2008), "Subdue’ing RHSEG: The Marriage of Graph-Based Knowledge Discovery (Subdue) with Image Segmentation Hierarchies (from RHSEG) for Data Analysis, Data Mining, and Knowledge Discovery." The project PI is Dr. James C. Tilton, NASA GSFC and the project Co-I is Dr. Diane J. Cook, Washington State University. This project is funded by NASA's Applied Information Systems Research project. In this project, Drs. Tilton and Cook will design and implement the integration of the Subdue graph-based knowledge discovery system developed at the University of Texas Arlington and Washington State University, with image segmentation hierarchies produced by the RHSEG software developed at NASA GSFC, and perform limited pilot demonstration studies of data analysis, mining, and knowledge discovery on NASA data. Subdue is a method for discovering substructures in structural databases. Subdue is devised for general-purpose automated discovery, concept learning, and hierarchical clustering with or without domain knowledge. However, for Subdue to be effective in finding patterns in imagery data, the data must be abstracted up from the pixel domain. An appropriate abstraction of imagery data is a segmentation hierarchy: a set of several 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. The RHSEG program, a recursive approximation to a Hierarchical Segmentation approach (HSEG), can produce segmentation hierarchies quickly and effectively for a wide variety of images. The HSEG/RHSEG approaches are based on region growing, and include a provision for merging spatially disjoint regions into aggregate regions. This region aggregation leads to a compact abstraction of even very complex images with very faithful representation of spatial detail. This proposed work is an innovative combination of two established information technologies which will significantly improve our ability to extract and/or discover information from imagery data. RHSEG is being utilized in the NASA-funded research project "MODIS Snow and Ice Product Suite: Maintenance, Enhancement, Error Analysis, and Validation," that was selected for funding for fiscal year 2008 by NASA's Science Mission Directorate. The project PI is Dr. Dorothy K. Hall, NASA GSFC and the project Co-I's are Dr. Vincent Salomonson, Univ. of Utah; Dr. George A. Riggs, SSAI; and Dr. James C. Tilton, NASA GSFC. The objective of this project is to maintain, enhance, validate, and refine the current suite of Terra and Aqua MODIS snow and sea ice algorithms to provide consistent, systematic measurements for science research, modeling, and for development of climate-data records of snow cover and sea ice surface temperature (IST).  List of Acronyms:
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
NASA has one issued patent and one pending patent application. Published patent:U.S. Patent #6,895,115: Method for implementation of recursive hierarchical segmentation on parallel computers (Link opens new browser windows.) A U.S. patent application (10/845,419) for "Method and System for Eliminating Processing Artifacts in Recursive Grouping Operations" is currently pending. On September 30, 2005, NASA filed a “continuation in part” to this application for a related technology, “A split-remerge method for eliminating processing window artifacts in recursive hierarchical segmentation.” Additional intellectual property:The Core RHSEG Pre-processing Software and the HSEGViewer are in the public domain. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
+ RHSEG Technical Information + RHSEG Applications + RHSEG Awards RHSEG Technical Information
The Recursive Hierarchical Segmentation Pre-Processing Software for Analyzing Imagery Data has received several awards including:
The Recursive Hierarchical Segmentation Pre-processing Software technology was also featured at the 2004 New Technology Reporting Awards Program held at the Newton White Mansion in Mitchellville, MD, because of successful transfer of the technology to Bartron Medical Imaging, LLC.
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
Check back for upcoming events
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
If you would like additional information or are interested in partnering with NASA for the commercialization of the RHSEG technology, please go to Register Your Interest, or contact: (304) 253-8537
Technology transfer and commercialization are an important part of the mission at NASA's Goddard Space Flight Center. Goddard's technology, expertise, and facilities are a national asset that can be used to develop new products and processes that benefit the United States. These benefits include increasing the Nation's competitiveness, improving the balance of trade, and enriching the lives of the citizenry. To ensure that these benefits are achieved, Goddard established the Technology Transfer Program (TTP).
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
Questions and answers will be posted as they are received. To submit a question, please go to Register Your Interest.
Q: What file formats are compatible with RHSEG? A: RHSEG expects input in band sequential, RAW format with no header data included.
Q: What if my data isn't in the correct format? A: A variety of third-party image conversion products exist. For example, ImageMagick is a popular free-ware solution that can convert TIFF to RAW.
Q: What size images can I process with RHSEG? A: Maximum image size is dependent on the amount of RAM available. With 1 Gigabyte of RAM, you can process images up to 8000 x 8000 pixels, with any number of bands and with the RHSEG rnb_level parameter set to 9 to allow for the most efficient processing. Note that larger images may require parallel processing.
Q: What image classification methods does RHSEG support? A: The HSEGViewer allows the user to manually classify and label regions with meaningful names (e.g., river, ground cover, buildings). RHSEG does not currently include any automated classification algorithms such as nearest neighbor, maximum likelihood, etc.
Q: RHSEG uses both spectral clustering and region growing to identify segments. Is there a way to control which of these two algorithms is weighted more heavily in the computations? A: Yes. RHSEG includes a parameter called spclust_wght. By varying its value, you can control both the relative importance of spectral clustering versus region growing in determining segments, as well as the required similarity between nonadjacent regions. See the RHSEG Help documentation (rhseg-help) for more details.
Q: What platforms are supported? A: RHSEG is avilable for licensing on both Windows and Unix platforms. By default, the trial version is available for Windows. Trials for Solaris or Linux are available on request.
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
