Benefits

The RHSEG suite offers the following benefits:

• Improved analytical capabilities: Optional weighted spectral clustering allows the grouping of similar but non-spatially adjacent regions. This feature provides more pixels to represent individual object classes present in the scene, providing a more robust representation of the object class. RHSEG can process two- or three-dimensional images.
  
  
• Increased speed: The divide-and-conquer approach of its recursive implementation combined with an innovative data-swapping scheme increases the speed of this computationally intensive program, making RHSEG practical even for extremely large data sets (e.g., remote sensing and medical images). Parallel implementation further increases the operational speed. The most cost-effective parallel platforms are PC clusters (e.g., Beowulf clusters) with 16, 64, or 256 CPUs.
  
  
• Refined results: The RHSEG suite presents results in a straightforward format consisting of a hierarchical set of image segmentations in either two or three spatial dimensions. This hierarchical presentation allows the user to select segmentations of interest and perform additional analyses.
  
  
• Maximized flexibility and control: Each hierarchical segmentation level has a number of partitioned regions. RHSEG provides unique flexibility and control to define the number of regions of interest, based on the purpose of the analysis (i.e., a user can choose the number of regions to maximize the relevant information for a particular analysis).
  
  
• Increased accuracy: Because the software maintains full spatial resolution at all region boundaries, RHSEG presents finer resolution of overall detail and a more accurate and reliable portrayal of the boundaries. The software accurately maintains image region boundaries regardless of the level of detail selected.
  
  
• Enhanced ease of use: The RHSEG suite includes an easy-to-use tool for viewing, analyzing, and understanding the output of the pre-processing software. Because users frequently prefer to analyze a single segmentation set that contains 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 selection of a specific data point, and it automatically highlights all corresponding data points for quick identification and labeling of specific image characteristics. Although the HSEGViewer can only directly view two-dimensional data, the user can select specific two-dimensional planes out of a three-dimensional data set for viewing.

Applications

Technology Details

What It Is

RHSEG partitions two- and three-dimensional image or image-like data into regions or clusters at various levels of detail. Using RHSEG, analysts can hierarchically relate regions of data at coarser levels of detail to regions of data at finer levels. After being processed by RHSEG 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. More information about how RHSEG works appears below. To understand the richness of RHSEG’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 hierarchical step-wise optimization (HSWO). The core hierarchical segmentation software (HSEG) approach is a hybrid of HSWO and spectral clustering. HSEG differs from HSWO in that it 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 also is unique because it enables the production of a segmentation hierarchy and allows options for different dissimilarity criteria.

A hierarchical set of image segmentations is one that is 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, the result of the HSEG approach is a hierarchical set of segmentations. It is possible to select a single segmentation out of the segmentation hierarchy by examining how the features of individual regions change throughout each level of detail.

The RHSEG Technology Suite

Dr. Tilton first began developing hierarchical segmentation technologies in 1983, after becoming familiar with earth sciences and remote sensing 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, because each pixel did not necessarily provide enough information about where it fitted 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. This theory ultimately led to the initial version of the core HSEG software algorithm.

The RHSEG suite now contains the following components. For information about how to access these components, see the “Licensing” section below.

Recursive Formulation (for parallel and single-processor computing platforms, for two- or three-dimensional images, and for non-image data)

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 or serial computing platforms. 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.

Parallel vs. Serial Computing: The implementation of RHSEG on parallel computing platforms 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 Thematic Mapper scene).

For those without access to parallel processing machines, NASA offers a version of RHSEG that uses an innovative data-swapping scheme to enable processing of larger image sets on single processor platforms. For example, a 6912-column, 6528-row, 6-band Landsat Thematic Mapper image can be processed in 8 hours, whereas previous versions were unable to process images of this magnitude. (The parallel version still is significantly faster, capable of processing the same image in only 1.5 minutes.)

Two- and Three-Dimensional Images: RHSEG can be used to analyze two- or three-dimensional data. Because processing three-dimensional data increases computational demands, NASA offers separate two-dimensional and three-dimensional versions, each with different licensing restrictions.

Non-Image Data: RHSEG also can process non-image data if it has image-like characteristics when plotted on a one-, two-, or three-dimensional array. Data has image-like characteristics when data points positioned nearer to each other in an array are more highly correlated than data positioned further away.

Artifact Elimination: All versions of RHSEG incorporate the patent-pending artifact elimination software, which avoids processing window artifacts caused by the RHSEG pre-processing software’s recursive subdivision and subsequent combination of the image data. This is accomplished by identifying pixels in the region that are more similar to pixels in the candidate region and either reassigning them to the region or splitting them out and remerging them after processing.

HSEGViewer

RHSEG’s output is a set of hierarchical segmentations. Most scientists, however, want a single segmentation to work with, rather than a set of segmentations. The problem is selecting the appropriate image segmentation from the hierarchical set. At times, this selection may 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 is more suitable. Therefore, an additional program, HSEGViewer is available to facilitate combining a number of the hierarchical segmentations into a single segmentation. This tool enables the user to view the RHSEG output, facilitating the selection of segmentation sets.

How it Works

The RHSEG software initially partitions 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 combined to form larger regions. Then, the user can compare pairs of non-spatially adjacent regions, and the user can combine pairs of non-spatially adjacent regions that are at least as similar as the previously compared spatially adjacent regions. This process continues until reaching a prespecified number of regions (depending on the coarseness or fineness of detail desired). At this point, RHSEG provides options for controlling the output of the segmentation hierarchy from that number of regions, down to a two-region segmentation.

RHSEG’s ability to produce a hierarchical set of segmentations is noteworthy and useful, 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 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"). This is why the program provides the choice of several levels of segmentation resolution. The following are samples of a segmented image as viewed using a differing 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 image, shot over central Washington, D.C.

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, D.C. 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), with some additional minor differentiation among building regions, and a number of other minor regions 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 necessarily the best choice for identifying all trends, patterns, or features of the data. Although 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 required.

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), an 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 may contain several lakes, separated by land. Because RHSEG 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/Performance

The RHSEG pre-processing software and HSEGViewer software algorithms have been tested for a variety of image segmentation applications for projects undertaken by NASA Goddard’s Computational and Information Sciences and Technology Office.

The table below compares 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 level of recursion and weighting parameters on processing time. Processing times of less than 2 minutes are obtained for images as large as 4096x4096 pixels (not shown) in the case where no nonadjacent merges are allowed (weighting factor of zero). In such a case, processing times are limited only by memory restraints. For cases where the nonadjacent region merge weighting factor is greater than zero, recursion is required to obtain processing times of less than 1 hour for all but the smallest image sizes. Here, processing times under 1 hour are found for images as large as 1024x1024 pixels with just one CPU. For images larger than 1024x1024 pixels, parallel processing is generally required for reasonable processing times. Processing images as large as 7000x7000 pixels is possible in well under 10 minutes, using 256 CPUs.

Patents

Published patent

U.S. Patent #6,895,115 (link opens new browser window): Method for implementation of recursive hierarchical segmentation on parallel computers

Pending patent application

A U.S. patent application (link opens new browser window) for "Split-Remerge Method for Eliminating Processing Artifacts in Recursive Hierarchical Segmentation" is 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.

A U.S. patent application (link opens new browser window) for “Systems, Methods, and Apparatus for D-Dimensional Formulation and Implementation of Recursive Hierarchical Segmentation” was filed on June 1, 2007

Additional intellectual property

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

Publications and Awards

RHSEG Technical Information

1. Segmentation of Complex Images by Best Merge Region Growing with Disjoint Region Aggregation, by James C. Tilton, submitted to Image and Vision Computing.
   
   
2. The Integration of Graph-Based Knowledge Discovery with Image Segmentation Hierarchies for Data Analysis, Data Mining and Knowledge Discovery, by James C. Tilton, Diane J. Cook, and Nikhil Ketkar, Proceedings of the 2008 International Geoscience and Remote Sensing Symposium, Boston, MA, July 7-11, 2008
   
   
3. Parallel Implementation of the Recursive Approximation of an Unsupervised Hierarchical Segmentation Algorithm (link opens new browser window), by James C. Tilton, Chapter 5 of the book High Performance Computing in Remote Sensing, C.-I. Chang and A. J. Plaza, editors, CRC Press, pp. 133-144, October 2007.
   
   
4. Analysis of hierarchically related image segmentations (link opens new browser window), 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
   
   
5. Image Information Mining Utilizing Hierarchical Segmentation (link opens new browser window), 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
   
   
6. Hierarchical Segmentation of Hyperspectral Data (link opens new browser window), by J. Anthony Gualtieri and James C. Tilton, 2002 AVIRIS Earth Science and Applications Workshop Proceedings, Pasadena, CA, March 5-8, 2002
   
   
7. Recursive Hierarchical Image Segmentation (PDF) (link opens new browser window), prepared for presentation at the NASA Advanced Technology Workshop: "New Partnerships in Medical Diagnostic Imaging," Greenbelt, MD, July 17-18, 2001
   
   
8. 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
   
   
9. A recursive PVM implementation of an image segmentation algorithm with performance comparisons in-between the HIVE and Cray T3E (link opens new browser window), 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
   
   
10. Image Segmentation by Region Growing and Spectral Clustering with a Natural Convergence Criterion (link opens new browser window), by James C. Tilton, Proceedings of the 1998 International Geoscience and Remote Sensing Symposium, Seattle, WA, pp. 1766-1768, July 6-10, 1998
    
    
11. Refining Image Segmentation by Integration of Edge and Region Data (link opens new browser window), Jacqueline Le Moigne and James C. Tilton, IEEE Transactions on Geoscience and Remote Sensing, Vol. 33, pp. 605-615, May 1995

RHSEG Applications

1. Recent Advances in Techniques for Hyperspectral Image Processing, by A. Plaza, J. A. Benediktsson, J. Boardman, J. Brazile, L. Bruzzone, G. Camps-Valls, J. Chanussot, M. Fauvel, P. Gamba, A. Gualtieri, M. Marconcini, J. C. Tilton, and G. Trianni, Remote Sensing of Environment, accepted for publication.
   
   
2. Enhancement of the MODIS Snow and Ice Product Suite Utilizing Image Segmentation, by James C. Tilton, Dorothy K Hall, and George A. Riggs, Proceedings of the 2008 International Geoscience and Remote Sensing Symposium, Boston, MA, July 7-11, 2008
   
   
3. Cloud Mask Generation for MODIS Utilizing Hierarchical Segmentations, by James C. Tilton, Proceedings of the 2006 International Geoscience and Remote Sensing Symposium, Denver, CO, USA, July 31–August 4, 2006.
   
   
4. Utilizing Hierarchical Segmentation to Generate Water and Snow Masks to Facilitate Monitoring Change with Remotely Sensed Image Data (link opens new browser window), by James C. Tilton, William T. Lawrence, and Antonio J. Plaza, GIScience & Remote Sensing, Vol. 43, No. 1, pp. 39-66, 2006.
   
   
5. Automated Selection of Results in Hierarchical Segmentations of Remotely Sensed Hyperspectral Images (link opens new browser window), by Antonio J. Plaza and James C. Tilton, Proceedings of the 2005 International Geoscience and Remote Sensing Symposium, Seoul, Korea, 25-29, July, 2005
   
   
6. A Pre-Attentive Vision Model for Data Prospecting (link opens new browser window), by Ivan A. Galkin, Grigori M. Khmyrov, Alexander V. Kozlov, Bodo W. Reinisch, James C. Tilton, Shing F. Fung, and Antonio Plaza; The 2nd International Conference on Cybernetics and Information Technologies, Systems and Applications: CITSA 2005, Orlando, Florida, USA, July 14-17, 2005
   
   
7. Monitoring Change through Hierarchical Segmentation of Remotely Sensed Image Data (link opens new browser window) (Powerpoint), by James C. Tilton and William T. Lawrence, MultiTemp 2005: 3^rd International Workshop on the Analysis of Multi-Temporal Remote Sensing Images, Biloxi, MS, USA, May 16-18, 2005
   
   
8. Processing Radio Plasma Imager Plasmagrams Utilizing Hierarchical Segmentation (link opens new browser window), by I. A. Galkin, G. Khmyrov, B. W. Reinisch, J. C. Tilton, and S. F. Fung, Proceedings of the 2004 Earth Science Technology Conference, Palo Alto, CA, June 22-24, 2004
   
   
9. Knowledge Discovery and Data Mining Based on Hierarchical Segmentation of Image Data (PDF) (link opens new browser window), presented by James C. Tilton for John Hopkins University’s Visionary Lecture Series in Discovery Informatics, Montgomery County Campus, Rockville, MD, April 19, 2004
   
   
10. Hierarchical Segmentation of Remotely Sensed Imagery Data using Massively Parallel GNU-LINUX Software (PDF) (link opens new browser window), 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
    
    
11. Recursive Hierarchical Image Segmentation by Region Growing and Constrained Spectral Clustering (PDF) (link opens new browser window), 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
    
    
12. Utilization of New Data Products based on Hierarchical Segmentation of Remotely Sensed Imagery Data in Earth Science Enterprise Applications (PDF) (link opens new browser window), 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
    
    
13. Hybrid Image Segmentation for Earth Remote-Sensing Data Analysis (link opens new browser window), by James C. Tilton, Proceedings of the 1996 International Geoscience and Remote Sensing Symposium (IGARSS '96), Lincoln, Nebraska, May 27-31, 1996
    
    
14. 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 Awards & Honors

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

• RHSEG and Bartron's Med-Seg were jointly selected for the 2008 World's Best Technologies Showcase (link opens new browser window), which was held in March 2008 in Arlington-DFW, Texas.
  
  
• James Kerley Award, April 4, 2006—"For efforts to find new uses for his Hierarchical Segmentation (HSEG) software, which he originally developed for remote sensing applications"
  
  
• Excellence in Information Science and Technology Award, May 18, 2005—"For best exhibiting broad, significant contributions to Goddard programs or projects in the areas of information science and technology. This award recognizes career achievement or a specific act of exceptional merit that was completed in the previous year."
  
  
• Space Act Award (link opens new browser window), 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 (link opens new browser window), September 16, 2004.
  
  
• 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 (link opens new browser window).
  
  
• $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.
  

.

Licensing and Partnering Options

Demo Software

To receive the free 90-day evaluation software, visit the Register Your Interest (link opens new browser window) page and fill out the required form, indicating the preferred platform.

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 us by phone or email: (919) 249-0327,