NASA Case No. GSC 14,331-1 was approved for Public Release and was classified as "releasable without a nondisclosure agreement" on May 30, 2000 by Ms. Myra J. Bambacus, Technology Commercialization Office, Code 750, Goddard Space Flight Center.
|National Aeronautics and Space Administration||Disclosure of Invention and New Technology (Including Software)||
|NT CONTROL NO. (OFFICIAL USE ONLY)
NASA Case No. GSC 14,331-1
|This is an
important legal document. Carefully complete and forward to the
Patent Representative (NASA in-house innovation) or New Technology
Representative (contractor/grantee innovation) at NASA. Use of this
report form by contractor/grantee is optional; however, an
alternative format must at a minimum contain the information
required herein. NASA in-house disclosures should be read,
understood and signed by a technically competent witness in the
witness signature block at the end of this form.
In completing each section, use whatever detail deemed appropriate for a "full and complete disclosure." Contractors/Grantees please refer to the New Technology or Patent Rights - Retention by the Contractor clauses. When necessary, attach additional documentation to provide a full, detailed description.
A Region Labeling Tool for use with Hierarchical Segmentation
James C. Tilton, Ph. D., Computer Engineer
(301) 286-9510 (W) and (301) 552-0012 (H)
6704 Cipriano Road, Lanham, MD 20706-3877
NASA's Goddard Space Flight Center
Earth and Space Data Computing Division (Code 930)
NASA's Goddard Space Flight Center
Applied Information Sciences Branch (Code 935)
Greenbelt, MD 20771
Innovator #1 Innovator #3
Innovator #2 Innovator #4
GE = Government
NASA Grant No. ________________________________
NASA Prime Contract No. ________________________
Task No. _____________ Report No. ________________
Subcontractor, Subcontract Tier _______________
(NASA prime contractor and NASA in-house)
Multiple Contractor Contribution
(collaboration of prime contractor and subcontractor)
Other (e.g., Space Act or Cooperative Agreement)
Contractor Reportable Item No. ____________________
A "Region Labeling Tool" has been developed to facilitate the selection of particular segmentations from the hierarchical set of segmentations output by the RHSEG (Recursive Hierarchical Segmentation) algorithm. For a complete description of the RHSEG algorithm see NASA Case No. GSC 14,328-1. Also see NASA Case No. GSC 14,305-1 for a complete description of the efficient implementation of the RHSEG algorithm on parallel computers. With this tool, an analyst can select a particular data point (based on an appropriate graphical representation of the original data), and all other data points in the same region (either at the finest level or coarsest level of detail) will be highlighted. The analyst can choose to adjust the level of segmentation detail by selecting other levels from the segmentation hierarchy. "Region of interest" and other tools are available to adjust the highlighted areas. Once the analyst is satisfied with the areas highlighted, he/she can label the segment with a particular alphanumeric phrase and color. This process can be continued until the whole data set is labeled. Other features of the Region Labeling Tool allow for a refinement of this process.
|NASA FORM 1679 JUL 98 REPLACES NF 425, NF 666, AND NF 666A, WHICH ARE OBSOLETE. Page 1 of 4|
|SECTION I -
DESCRIPTION OF THE PROBLEM OR OBJECTIVE THAT MOTIVATED THE
INNOVATION'S DEVELOPMENT (Enter as appropriate: A. - General
description of problem/objective; B. - Key or unique problem
characteristics; C. - Prior art, i.e., prior techniques, methods,
materials, or devices performing function of the innovation, or
previous means for performing function of software; and D. -
Disadvantages or limitation of prior art.)
A.- General description of problem/objective:
Segmentation, the partitioning of a data into related sections or regions, is a key first step in a number of approaches to data analysis and compression. In data analysis, the group of data points contained in each region provides a good statistical sampling of data values for more reliable labeling based on data feature values. In addition, the region shape can be analyzed as an additional clue for the appropriate labeling of the region. In data compression, the regions form a basis for compact representation of the data. The quality of the prerequisite data segmentation is a key factor in determining the level of performance of most of these data analysis and compression approaches.
Determining the best possible data segmentation for a given level of detail is an impossible task with current technology. However, excellent data segmentation results can be obtained with the hybrid of region growing and spectral clustering disclosed under NASA Case No. GSC 14,328-1, even though it can only be shown to be stepwise optimal. However, for even moderately sized data sets, this approach leads to a combinatorial explosion of computations making it impractical. This combinatorial explosion is overcome somewhat by the recursive formulation of this segmentation approach, also disclosed under NASA Case No. GSC 14,328-1. For moderate to large data sets, practical processing times are only possible with a carefully crafted recursive implementation of this algorithm on parallel computers, such as disclosed under NASA Case No. GSC 14,305-1.
Different applications require different levels of segmentation detail, and a particular application may require different levels of segmentation detail depending on the data objects being segmented. Thus, a choice of several levels of segmentation detail may be useful. The segmentation approach disclosed in NASA Case No. GSC 14,328-1 produces a hierarchical set of segmenations, based on natural convergence points. An analyst can pick and choose between the segmentations at different levels in the segmentation hierarchy to produce the most appropriate segmentation for the particular application.,/p>
This Disclosure of Invention and New Technology describes the look and feel of a software package developed to assist in the selection of the most appropriate segmention from the segmentation hierarchy for a particular application. The graphical user interface of the software package being described was developed using a particular third-party software development package. However, one should be able to port the look and feel of this software package to other third-party software development packages.
B. - Key or unique problem characteristics:
NASA Case No. 14,328-1 describes a hybrid image segmentation approach based on region growing and spectral clustering. This approach produces a hierarchically related set of image segmentations in which the regions may consist of non-spatially connected objects. In the current Disclosure of Invention and New Technology, we describe a "Region Labeling Tool" that can be used produce customized image labelings. With this tool, an analyst can select a particular data point (based on an appropriate graphical representation of the original data, e.g. RGB band combinations, band ratios, NDVI) and all other data points in the same region will be highlighted from either the most detailed or coarsest segmentation. The analyst then can adjust the level of segmentation detail by selecting other levels from the segmentation hierarchy. "Region of interest" and other tools are available to adjust the highlighted areas. Once the analyst is satisfied with the areas highlighted, he/she can label the segment with an alphanum eric phrase and color. This process can be continued until the whole data set is labeled. In section II. B. below, we demonstrate the Region Labeling Tool in a land cover analysis of a Landsat Thematic Mapper (TM) data set over the Baltimore, MD and Washington, DC area. We have seen that a key benefit of the using the Region Labeling Tool with hierarchical segmentation is that a much fuller utilization of the spectral and spatial information content of the Landsat TM data is obtained than that possible with conventional analysis techniques.
C. - Prior art, i.e., prior techniques, methods, materials, or devices performing function of the innovation, or previous means for performing function of software:
I am not aware of any previously developed software package that assists an analyst in selecting an appropriate unique image segmentation from a hierarchical set of image segmentations.
D. - Disadvantages or limitation of prior art: (Not applicable)
|SECTION II -
TECHNICALLY COMPLETE AND EASILY UNDERSTANDABLE DESCRIPTION OF
INNOVATION DEVELOPED TO SOLVE THE PROBLEM OR MEET THE
OBJECTIVE(Enter as appropriate; existing reports, if available,
may form a part of the disclosure, and reference thereto can be
made to complete this description: A. - Purpose and description of
innovation/software; B. - Identification of component parts or
steps, and explanation of mode of operation of innovation/software
preferably referring to drawings, sketches, photographs, graphs,
flow charts, and/or parts or ingredient lists illustrating the
components; C. - Functional operation; D. - Alternate embodiments
of the innovation/software; E. - Supportive theory; F. -
Engineering specifications; G. - Peripheral equipment; and H. -
Maintenance, reliability, safety factors.)
A. - Purpose and description of innovation/software:
The purpose of the software/innovation described herein is to assist an analyst in the selection of the most appropriate segmentation for a particular application from the segmentation hierarchy provided by the Hiearchical Segmentation (HSEG) program disclosed under NASA Case Nos. 14,305-1 and 14,328-1. While the initial application is to Earth science analysis of single-band, multispectral or hyperspectral remotely sensed imagery data of the Earth, the software/innovation also has applications to image data compression for image data archives, data mining (searching for particular shapes of objects with certain feature vector characteristics), and data fusion (based on matching region features between data sets from different times and/or different sensors). Potential applications outside of remote sensing are the analysis of imagery for medical applications, for nondestructive evaluation in manufacturing quality control, and for land mine detection.
B. - Identification of component parts or steps, and explanation of mode of operation of innovation/software preferably referring to drawings, sketches, photographs, graphs, flow charts, and/or parts or ingredient lists illustrating the components:
C. - Functional operation:
A functional description is not appropriate for this Disclosure of Invention and New Technology. This software package is written using a third-party software package, the Khoros Pro 2000 Software Developer's Kit, so key parts of this program's functionality are entangled with this third-party software package. The intent of this disclosure is to describe only the look and feel of the software package so that other software developers can, if they so choose, implement a software package with similar look and feel using some other software development package. If appropriate, one can also use the version we have developed under the Khoros Pro 2000 Software Developer's Kit, which we will make available under a suitable agreement.
D. - Alternate embodiments of the innovation/software: (Not applicable)
E. - Supportive theory: (Not applicable)
F. - Engineering specifications: (Not applicable)
G. - Peripheral equipment:
The Region Labeling Tool is written in the "C" programming language, compiled under the gcc version 2.8.1 compiler, under the Solaris 7 operating system on a SUN Workstation. However, this software should both compile and run using other "C" compilers under other UNIX-type operating systems, possibly with minor modifications.
H. - Maintenance, reliability, safety factors: (Not applicable)
|NASA FORM 1679 JUL 98 REPLACES NF 425, NF 666, AND NF 666A, WHICH ARE OBSOLETE. Page 2 of 4|
|SECTION III - UNIQUE
OR NOVEL FEATURES OF THE INNOVATION AND THE RESULTS OR BENEFITS OF
ITS APPLICATION (Enter as appropriate: A. - Novel or unique
features; B. - Advantages of innovation/software; C. - Development
or new conceptual problems; D. - Test data and source of error; E.
- Analysis of capabilities; and F. - For software, any re-use or
re-engineering of existing code, use of shareware, or use of code
owned by a non-federal entity.)
A. - Novel or unique features:
Most image segmentation approaches output a single image segmentation. However, the HSEG approach disclosed under NASA Case Nos. 14,305-1 and 14,328-1 outputs a hierarchical set of image segmentations, providing a choice in segmentation detail. The software package disclosed herein is an interactive software tool that can be used to select an appropriate image segmentation from the image segmentation hierarchy for a particular application. I have not seen any other published material in which the hierarchical nature of the segmentations is explicitly exploited in this manner.
B. - Advantages of innovation/software:
It is generally difficult to determine at what point to terminate region growing (where the process converges) in most region growing approaches to segmentation. The hierarchical set of segmentations produced by this approach eliminates the need to determine a single convergence point. However, it is difficult to directly select a single segmentation result from a set of hierarchical segmentations. The software package disclosed herein provides graphical assistance that enables an analyst to straightforwardly select an appropriate single segmentation from a segmentation hierarchy. The package is designed to take advantage of human visual and interactive capabilities without involving the human in a detailed analysis of the data.
C. - Development or new conceptual problems: (N/A)
D. - Test data and source of error: (N/A)
E. - Analysis of capabilities: (N/A)
F. - For software, any re-use or re-engineering of existing code, use of shareware, or use of code owned by a non-federal entity:
The software package described herein uses code owned by a non-federal entity: The Khoros Pro 2000 Software Developer's Kit. Khoros is a registered trademark of Khoral Research, Inc., 6200 Uptown Blvd, N. E., Suite 200, Albuquerque, NM 87110-4142, USA, phone 505-837-6500, fax 505-881-3842, url www.khoral.com. Khoros Pro 2000 is a trademark of Khoral Research, Inc. Use, duplication, or disclosure by the U. S. Government is subject to restrictions set forth in subparagraphs (a) through (d) of the Commercial Computer Restricted Rights clause of FAR 52.227-19 (June 1987) when applicable, or in the Commercial Computer Software paragraph in DFARS 227-7202 (June 1995), and in similar clauses in the NASA FAR Supplement.
The disclosure provided herein concentrates on the look and feel of the software package. This description is intended to assist in the porting of this software package to other software development systems besides the Khoros Pro 2000 Software Developer's Kit.
|SECTION IV -
SPECULATION REGARDING POTENTIAL COMMERCIAL APPLICATIONS AND POINTS
OF CONTACT (Including names of companies producing or using
During August and September of 1999, representatives of ERMapper and Research Systems, Inc. expressed interest in incorporating the HSEG and RHSEG algorithms and software similar to the Region Labeling Tool described herein into their software packages. The discussion with ERMapper was carried out through a third party, Jon Lang, a student at the University of Connecticut who uses ERMapper software for Earth science analysis. Jon relayed that ERMapper was very interested in the Region Labeling Tool, and provided an E-mail address (email@example.com) for Mr. Stuart Nixon, founder of ERMapper, but no direct discussions have been held with Mr. Nixon.
In early September 1999, I took a course on the ENVI software package marketed by Research Systems, Inc. I briefly discussed the recursive hierarchical segmentation algorithm and related region labeling tool with the instructor, Roberta Yuhas (her E-mail address is Roberta.Yuhas@cses.colorado.edu). She also read a preliminary description of the Region Labeling Tool. Ms. Yuhas indicated that Research Systems, Inc. would be very interested in incorporating the HSEG and RHSEG algorithms and software similar to the Region Labeling Tool into their ENVI software package.
Names and points of contact of companies who could potentially incorporate the Region Labeling Tool program into their software packages:
|NASA FORM 1679 JUL 98 REPLACES NF 425, NF 666, AND NF 666A, WHICH ARE OBSOLETE. Page 3 of 4|
TITLE PAGE DATE
(See Section 15 below)
Modification to Existing Technology X Substantial Advancement in the Art Major Breakthrough
Concept Only Design X Prototype Modification Production Model X Used in Current Work
Development started in mid-1996, and continued through September 1999.
Projected uses of the Region Labeling Tool described herein were discussed previously in a white paper to NASA's Earth Science Enterprise:
James C. Tilton, "Utilization of new data products based on hierarchical segmentation of remotely sensed imagery data in Earth Science Enterprise applications," submitted to NASA's Earth Science Enterprise in response to RFI 10-00007, May 14, 1999.
Ongoing collaborative research using the Region Labeling Tool, and involving James C. Tilton, NASA's GSFC and William T. Lawrence, Bowie State University, will be described in a paper in the upcoming International Geoscience and Remote Sensing Symposium (IGARSS''00), which will be held in Honolulu, Hawaii in July 2000:
|(a.) Using outsiders to
beta-test code? _ YES X
NO If Yes, done under beta-test agreement? _ YES
(b.) Modifications to this software continue by civil servant and/or contractual agreement? X YES _ NO
(c.) Previously copyrighted? _ YES X NO _ UNKNOWN If copyrighted, then by whom? _____________________
(d.) Were prior versions distributed? X YES _ NO If Yes, supply NASA or Contractor contact: Dr. William T. Lawrence,
Natural Sciences, Bowie State University, Bowie, MD 20715, phone (301) 464-6121, e-mail firstname.lastname@example.org.
(e.) Contains or is based on code owned by a non-federal entity? X YES _ NO _ UNKNOWN
If Yes, has a license for use been obtained? X YES _ NO _ UNKNOWN
(f.) Has the latest version been distributed without restrictions as to use or disclosure for more than one year?
_ YES X NO _ UNKNOWN If Yes, date of disclosure: _______________
|a. First disclosure to others||07/98||IGARSS'98, Seattle, WA|
|b. First sketch, drawing, logic chart or code||07/98||IGARSS'98, Seattle, WA|
|c. First written description||07/98||IGARSS'98, Seattle, WA|
|d. Completion of first model of full size device (invention) or beta version (software)||08/98||NASA's GSFC|
|e. First successful operational test (invention) or alpha version (software)||09/99||Bowie State University|
|f. Contribution of
innovators (if jointly developed, provide the contribution of
Developed by James C. Tilton, Code 935 (Applied Information Science's Branch), NASA's Goddard Space Flight Center, Greenbelt, MD USA 20771. During the summers of 1998 and 1999, Bowie Statue University students JoAnna P. Graham and Di Kang worked with me on the Region Labeling Tool, and some of their work was incorporated into the current version of the software. Their work helped to improve the efficiency of the implementation and/or the graphical user interface. However, this work was under my direction and not original or inventive in nature.
|g. Indicate any past,
present, or contemplated government use of the innovation
This software will be used to support collaborative research involving James C. Tilton, NASA's GSFC and William T. Lawrence, Bowie State University, which will be discussed in a paper "Interactive Analysis of Hierarchical Segmentation" at IGARSS'00 in July 2000.
|TYPED NAME AND SIGNATURE
(Innovator # 1)
James C. Tilton
|DATE||TYPED NAME AND SIGNATURE (Innovator # 2)||DATE|
|TYPED NAME AND SIGNATURE
(Innovator # 3)
|DATE||TYPED NAME AND SIGNATURE (Innovator # 4)||DATE|
|TYPED NAME AND SIGNATURE
(Witness # 1)
William J. Campbell
|DATE||TYPED NAME AND SIGNATURE (Witness # 2)||DATE|
|NASA FORM 1679 JUL 98 REPLACES NF 425, NF 666, AND NF 666A, WHICH ARE OBSOLETE. Page 4 of 4|