Background

Benefits

Applications

System Requirements and Demo

Technology Details

Patents

Publications and Awards

Licensing and Partnership Options

Printable Brochure

Upcoming Events

Contact Information

Register Your Interest

Frequently Asked Questions

Background

Benefits

Applications

System Requirements and Demo

Benefits

The RHSEG Pre-processing Software and HSEGViewer produce a number of benefits. These include the following:

• Improved analytical capabilities: Optional weighted spectral clustering allows the grouping of similar but non-spatially adjacent regions. This feature gives the user more pixels to represent the object in the scene and provides a more robust representation of the object.
  
  
• Increased speed: The divide-and-conquer approach of the recursive implementation, combined with a newly implemented data swapping scheme, increases the speed of this computationally intensive program, making use of the RHSEG Pre-processing Software practical even for extremely large data sets (e.g., remote sensing and medical images). Parallel implementation further increases speed of operation. The most cost effective parallel platforms are PC clusters (e.g., Beowulf clusters) with 16, 64, or 256 CPUs.
  
  
• Refined results: The RHSEG Pre-processing Software presents its results in a straightforward format consisting of a hierarchical set of image segmentations. This hierarchical presentation of results allows the user to choose the segmentation(s) of interest and to perform additional analyses.
  
  
• Flexibility and control: Each hierarchical segmentation level consists of a number of segmented regions. The RHSEG Pre-processing Software provides the user with the flexibility and control to define the number of regions of interest based on the purpose of the analysis (i.e., the user chooses the number of regions to maximize the relevant information for his/her particular analysis).
  
  
• Accuracy: Because the software maintains full spatial resolution at all region boundaries, the RHSEG Pre-processing Software provides finer resolution of overall detail and a more accurate and reliable portrayal of the boundaries. The software accurately maintains image regions regardless of the level of detail.
  
  
• Ease of use: The HSEGViewer is an easy-to-use tool for viewing, analyzing, and understanding the output of the RHSEG Pre-processing Software. Since users frequently prefer to analyze a single segmentation set containing all relevant data, the HSEGViewer allows an analyst to synthesize such a set by combining segmentation sets from a number of hierarchical segmentations. Additionally, this tool allows the user to select a specific data point and automatically highlight all corresponding data points for quick identification and labeling of specific characteristics of an image.
  

Background

Benefits

Applications

System Requirements and Demo

Technology Details

Patents

Publications and Awards

Licensing and Partnership Options

Printable Brochure

Upcoming Events

Contact Information

Register Your Interest

Frequently Asked Questions

Applications

Background

Benefits

Applications

System Requirements and Demo

Technology Details

Patents

Publications and Awards

Licensing and Partnership Options

Printable Brochure

Upcoming Events

Contact Information

Register Your Interest

Frequently Asked Questions

System Requirements and Demo Software

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.

Technology Details

What It Is

The Recursive Hierarchical Segmentation (RHSEG) Pre-processing Software is an approach for partitioning two-dimensional imagery 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 Background

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.

HSEG Development History

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.

Three-dimensional and Nonspatial Data

It has also been found that the RHSEG approach can be generalized to analyze three-dimensional or higher dimension data, as well as nonspatial data. However, the currently available version of RHSEG is limited to analyzing two-dimensional image data, and nonimage data that can be cast in a two-dimensional image format. The image data may have any number of spectral bands.

The latest version of RHSEG also includes the ability to specify convergence criteria, which determines the rate at which segmentation results are saved into the output segmentation hierarchy.

How it Works

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 ratio between the maximum merging thresholds 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:

Figure 1 (a) Original Landsat TM image over central Washington, DC

(b) 7-region level from segmentation hierarchy

(c) 12-region level from the segmentation hierarchy

(d) 25-region level from segmentation hierarchy

(e) 50-region level from segmentation hierarchy

(f) 11 regions selected from the 7-region, 25-region, and 50-region levels of the segmentation hierarchy

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 significance of optionally allowing the combination of non-spatially adjacent regions can be highlighted by an earth satellite image example. An earth satellite image might contain several lakes separated by land. Because the RHSEG Pre-processing Software allows the grouping of similar regions that are not necessarily spatially adjacent, not only will the individual lakes be identified at one segmentation level within the hierarchy, but all lake regions (including the non-spatially adjacent ones) will be grouped together into another composite region (at another segmentation level within the hierarchy).

Testing

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) with a 2.4 GHz processor, on a six-band Landsat Thematic Mapper data set. The results shown 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 7000x6500 can be processed in well under 10 minutes using 256 CPUs.

* Default value for this image size.

See RHSEG Release Notes for newly updated run times.

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.

List of Acronyms

Patents

NASA has filed two patent applications, one of which is published, relating to the parallel and artifact elimination components of the HSEG technology.

Published patent:

U.S. Patent #6,895,115: Method for implementation of recursive hierarchical segmentation on parallel computers [Link opens new browser windows.]

Pending patent application:

A U.S. patent application for "Method and System for Eliminating Processing Artifacts in Recursive Grouping Operations" is currently pending.

Additional intellectual property:

The Core RHSEG Pre-processing Software and the HSEGViewer are in the public domain.

Background

Benefits

Applications

System Requirements and Demo

Technology Details

Patents

Publications and Awards

Licensing and Partnership Options

Printable Brochure

Upcoming Events

Contact Information

Register Your Interest

Frequently Asked Questions

Publications and Awards

RHSEG Technical Information

[All links open new browser windows.]

1. Hierarchical Image Segmentation by Recursive Hierarchical Step-Wise Optimization and Constrained Spectral Clustering, by James C. Tilton, to be submitted to IEEE Transactions on Image Processing. (Link to be added when available.)
   
   
2. Analysis of hierarchically related image segmentations, by James C. Tilton, Proceedings of the IEEE Workshop on Advances in Techniques for Analysis of Remotely Sensed Data, Greenbelt, MD, USA, Oct. 27-28, 2003
   
   
3. Image Information Mining Utilizing Hierarchical Segmentation, by James C. Tilton, Giovanni Marchisio, Krzystof Koperski, and Mihai Datcu; Proceedings of the 2002 International Geoscience and Remote Sensing Symposium, Toronto, ON, Canada, Vol. II, pp. 1029-1031, June 24-28, 2002
   
   
4. Hierarchical Segmentation of Hyperspectral Data, by J. Anthony Gualtieri and James C. Tilton, 2002 AVIRIS Earth Science and Applications Workshop Proceedings, Pasadena, CA, March 5-8, 2002
   
   
5. Recursive Hierarchical Image Segmentation (PDF), prepared for presentation at the NASA Advanced Technology Workshop: "New Partnerships in Medical Diagnostic Imaging," Greenbelt, MD, July 17-18, 2001
   
   
6. Interactive Analysis of Hierarchical Segmentation, by James C. Tilton and William T. Lawrence, Proceedings of the 2000 International Geoscience and Remote Sensing Symposium, Honolulu, HI, July 24-28, 2000
   
   
7. A recursive PVM implementation of an image segmentation algorithm with performance comparisons in-between the HIVE and Cray T3E, by James C. Tilton, Proceedings of the Seventh Symposium on the Frontiers of Massively Parallel Computation, Annapolis, MD, pp. 146-153, Feb. 21-25, 1999
   
   
8. Image Segmentation by Region Growing and Spectral Clustering with a Natural Convergence Criterion, by James C. Tilton, Proceedings of the 1998 International Geoscience and Remote Sensing Symposium, Seattle, WA, pp. 1766-1768, July 6-10, 1998
   
   
9. Refining Image Segmentation by Integration of Edge and Region Data, Jacqueline Le Moigne and James C. Tilton, IEEE Transactions on Geoscience and Remote Sensing, Vol. 33, pp. 605-615, May 1995

RHSEG Applications

1. Knowledge Discovery and Data Mining Based on Hierarchical Segmentation of Image Data (PDF), presented by James C. Tilton for John Hopkins University’s Visionary Lecture Series in Discovery Informatics, Montgomery County Campus, Rockville, MD, April 19, 2004.
   
   
2. Hierarchical Segmentation of Remotely Sensed Imagery Data using Massively Parallel GNU-LINUX Software (PDF), presented by James C. Tilton at the X Congreso Nacional de Teledetección (10th Spanish Remote Sensing Conference), Cáceres, Spain, September 17-19, 2003.
   
   
3. Recursive Hierarchical Image Segmentation by Region Growing and Constrained Spectral Clustering (PDF), presented by James C. Tilton at the EUSC-ESA Joint Seminar on Knowledge Driven Information Management in Earth Observation Data, Frascati, Italy, December 5-6, 2002.
   
   
4. Utilization of New Data Products based on Hierarchical Segmentation of Remotely Sensed Imagery Data in Earth Science Enterprise Applications (PDF), by James C. Tilton, white paper to NASA HQ's Earth Science Enterprise in response to the Advanced Information Technology Request For Information (RFI) 10-00007, May 14, 1999
   
   
5. Hybrid Image Segmentation for Earth Remote-Sensing Data Analysis, by James C. Tilton, Proceedings of the 1996 International Geoscience and Remote Sensing Symposium (IGARSS '96), Lincoln, Nebraska, May 27-31, 1996
   
   
6. Iterative Parallel Region Growing on the MasPar MP-2, by James C. Tilton. Poster paper presented at the "5th Symposium on the Frontiers of Massively Parallel Computation," McLean, VA, Feb. 6-9, 1995

RHSEG Pre-processing Software Awards & Honors

The Recursive Hierarchical Segmentation Pre-Processing Software for Analyzing Imagery Data has received several awards including:

• Space Act Award, August 16, 2004-"For the creative development of exceptional scientific and technical contributions which have been determined to be of significant value in the advancement of the aerospace technology program of NASA, entitled: Hierarchical Image Segmentation, its Recursive Formulation, and the Associated HSEGViewer Program"
  
  
• The Regional Excellence in Technology Transfer Award by the Federal Laboratory Consortium Mid-Atlantic Region, September 16, 2004.
  
  
• $150K in funding for the "Improving the Commericialization Potential of Hierarchical Segmentation Software" in 2002 and 2003, from the Commercial Technology Development (CTD) Program of GSFC’s Technology Commercialization Office.

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

.

Background

Benefits

Applications

System Requirements and Demo

Technology Details

Patents

Publications and Awards

Licensing and Partnership Options

Printable Brochure

Upcoming Events

Contact Information

Register Your Interest

Frequently Asked Questions

Licensing and Partnering Options

As outlined in the Code of Federal Regulations, NASA is offering companies both nonexclusive and exclusive licenses:

Nonexclusive: It is U.S. government policy to make government technology as widely available to U.S. industry as possible. Therefore, the preferred licensing arrangement is a nonexclusive license. See the NASA Headquarters Model Nonexclusive Patent License Agreement Web site for an example.

Exclusive: In some instances, an exclusive license is appropriate. In such cases, NASA may grant limited field-of-use exclusive licenses. Granting of any exclusivity requires a public announcement in the Federal Register followed by a 15-day waiting period. See the NASA Headquarters Model Exclusive Patent License Agreement Web site for an example.

Partnering Options

NASA offers two partnering options.

NASA/Industry Collaboration: In addition to licensing, there are several other ways a company can work with NASA to access NASA-developed technology. Typically, a working relationship is formalized as a Space Act Agreement (either reimbursable or non-reimbursable). The Space Act Agreement is similar to a Cooperative Research and Development Agreement (CRADA) used by other federal agencies.

Informal Technical Consultation: NASA technical experts are available for informal/quick response technical consultation on a limited basis. See the Contact Information section for phone, e-mail, and fax information, or go to Register Your Interest.

Confidentiality

As employees of the federal government, NASA employees are bound by Title 18 United States Code Section 1905 (18 U.S.C. 1905) to protect proprietary company information, including proprietary company information disclosed in a license application.

Upcoming Events

Contact Information

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:

Frequently Asked Questions