| Skip to content | |||||
 |
|
||||
 |
|||||
 |
|
||||
Featured Technologies  |
 |
|||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
For faster, highly accurate processing of high-resolution images and other complex data sets in 2D and 3D
The Recursive Hierarchical Segmentation (RHSEG) suite of technologies, developed by NASA Goddard Space Flight Center’s Dr. James C. Tilton, provides hierarchical segmentation (pre-processing) of image and image-like data. The RHSEG suite significantly improves the extraction of patterns from complex data sets. Optimized for speed and accuracy, it 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 within a wide range of data types. Images can be two-dimensional or three-dimensional single-band, multispectral, or hyperspectral data at resolutions up to 16000x16000 pixels. Originally designed for remote earth sensing, the RHSEG suite is broadly applicable to a wide range of applications, from medical image analysis to image data mining. NASA Goddard invites companies, universities, and other government laboratories to license RHSEG technologies. Details about the RHSEG technology suite, and information about licensing and/or obtaining a demonstration copy of the software appear below.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
The RHSEG suite offers the following benefits:
|
|||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
+ Project Use of RHSEG The RHSEG suite is useful for pre-processing image and image-like data for further intelligent analysis. Possible applications for RHSEG include, but are not limited to:
Project Use of RHSEGNASA has used RHSEG software in several projects. 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 was a key technology in a NASA research project funded for fiscal year 2008 (October 2007–September 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 principal investigator was Dr. James C. Tilton of NASA Goddard Space Flight Center, and the co-investigator was Dr. Diane J. Cook of Washington State University. Seed funding for this project came from NASA's Applied Information Systems Research Program. Drs. Tilton and Cook investigated the design and implementation of 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 RHSEG. Subdue is a method for discovering substructures in structural databases. Subdue was devised for general-purpose automated discovery, concept learning, and hierarchical clustering, with or without domain knowledge. For Subdue to be effective in finding patterns in imagery data, the data must be abstracted up from the pixel domain through image segmentation. RHSEG was an excellent choice because it provided the image segmentations required for input to Subdue, based on three key factors: (1) the high spatial fidelity of image segmentations produced by RHSEG, (2) the ability of RHSEG to automatically group spatially connected region objects into region classes, and (3) the hierarchical set of image segmentations that RHSEG automatically produced. This seed project took some important initial steps in translating image segmentations into relational graphs for analysis by Subdue, achieving some limited data analysis success. The grouping of region objects into region classes, provided by RHSEG, proved important in this translation. The seed project also clarified the importance of enabling Subdue to utilize region object size and region object neighbor relationship information. This is one of the key elements of a follow-on proposal to NASA’s Applied Information Systems Research Program, “Object-Based Image Analysis for Data Analysis, Data Mining and Knowledge Discovery.” Another element of this proposed project seeks to enable Subdue to utilize directly the RHSEG-provided segmentation hierarchy. NASA is expected to make the funding announcement for this follow-on proposal in spring 2009. MODIS Snow and Ice Product Suite: Maintenance, Enhancement, Error Analysis, and Validation RHSEG is being utilized in the NASA-funded research project, "MODIS Snow and Ice Product Suite: Maintenance, Enhancement, Error Analysis, and Validation," selected for funding in fiscal year 2008 by NASA's Science Mission Directorate. The principal investigator was Dr. Dorothy K. Hall, NASA Goddard Space Flight Center, and the co-investigators were Dr. Vincent Salomonson, University of Utah; Dr. George A. Riggs, Science Systems and Applications, Inc., and Dr. James C. Tilton, NASA Goddard Space Flight Center. 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). Automating and Enhancing Protocols for the Development of Signatures for Archaeological Sites Using Publicly Available NASA Imagery RHSEG is being used to find and study archeology sites—an effort funded through the NASA Space Archaeology Program. Cultural Site Research and Management (CSRM), a private company, contracts with the Department of Defense to help U.S. Navy and Marine Corps produce archaeological surveys. The company uses RHSEG to test a number of approaches to improving the accuracy of archaeological site identification, including the elimination of “noise,” with the goal of reducing false-positive signatures. CSRM is working at a World Heritage site in Petra, Jordan, at Mayan and Inca sites in Central America, and at a North American Indian site in Bluff, Utah. The company seeks to identify and preserve such sites, and to help understand the history of environmental change and the ways in which human alterations of the landscape have precipitated that change and, in some cases, environmental collapse.
RHSEG has been nonexclusively licensed to Bartron Medical Imaging, LLC (link opens new browser window). Since launching its medical imaging product, Med-Seg™, Bartron has reported that RHSEG has enabled the company to successfully analyze and extract from grayscale data meaningful and significant features previously indistinguishable by the human eye. Read more about Bartron’s successful use of RHSEG.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
+ 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 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.
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.
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.
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).
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.
Nonadjacent region merging weighting factor = 0.1
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 (link opens new browser window) is a popular freeware solution that can convert TIFF to RAW. OpenEV (link opens new browser window) is also very useful for this purpose.
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 8,000 by 8,000 pixels with any number of bands and with the RHSEG rnb_levels parameter set to 9 to allow for the most efficient processing. Images as large as 16,000 by 16,000 pixels have been processed on parallel machines at the NASA Center for Computational Sciences (link opens new browser window). 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). Currently, RHSEG does not 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, the user can control both the relative importance of spectral clustering versus region growing in determining segments, as well as the required similarity between nonadjacent regions. More information is provided in the RHSEG Help documentation. To obtain a copy, please see the Register Your Interest page.
Q: What platforms are supported? A: RHSEG licensing is available for both Windows and Linux/Unix platforms. By default, the trial version is available for Windows. Trials for Solaris Unix or certain implementations of Linux are available on request.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
NASA has one issued patent and two pending patent applications. The RHSEG suite also includes other intellectual property. Published patent:U.S. Patent #6,895,115 (link opens new browser window): Method for implementation of recursive hierarchical segmentation on parallel computers 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. |
|||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
+ RHSEG Technical Information + RHSEG Applications + RHSEG Awards & Honors RHSEG Technical Information
The Recursive Hierarchical Segmentation Pre-Processing Software for Analyzing Imagery Data has received several awards including:
|
|||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
RHSEG is available for licensing in two versions:
To start the licensing process or to submit a request to receive a 90-day evaluation version, visit the Register Your Interest page. For more information related to technology licensing/partnering with NASA Goddard Space Flight Center, please visit the Licensing and Partnering (link opens new browser wiindow) page. |
|||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
NASA is offering 90-day evaluation copies of the RHSEG software to help demonstrate the program’s capabilities. It is available for Windows, Solaris Unix, and various Linux non-parallel systems. (No demo is available for the parallel version of RHSEG.) To receive the free 90-day evaluation software, visit the Register Your Interest page and fill out the required form, indicating the preferred platform.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
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
|
|||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||
