TEXT VERSION

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.

 
NASA Logo National Aeronautics and Space Administration Disclosure of Invention and New Technology (Including Software)
Form Approved
O.M.B. NO.
2700-0009
DATE

02/29/00

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.

  1. DESCRIPTIVE TITLE
A Region Labeling Tool for use with Hierarchical Segmentation
  1. INNOVATOR(S) (Name(s), Title(s), Phone Number(s), Home Address(es). For non-U.S. citizen, include INS Form I-551 No. and expiration date. If multiple innovators, please number.
James C. Tilton, Ph. D., Computer Engineer
(301) 286-9510 (W) and (301) 552-0012 (H)
6704 Cipriano Road, Lanham, MD 20706-3877
  1. EMPLOYER(S) WHEN INNOVATION MADE (Name and Division)
NASA's Goddard Space Flight Center
Earth and Space Data Computing Division (Code 930)
  1. ADDRESS(ES) (Place of performance)
NASA's Goddard Space Flight Center
Applied Information Sciences Branch (Code 935)
Greenbelt, MD 20771
  1. EMPLOYER STATUS (choose one for each innovator)
        GE              _________
Innovator #1  Innovator #3

  _________       _________
Innovator #2  Innovator #4

GE = Government
CU = College or University
NP = Non-Profit Organization
SB = Small Business Firm
LE = Large Entity

  1. ORIGIN (check all that apply and supply number(s))
X      NASA In-house Org. Code      935    
          NASA Grant No. ________________________________
          NASA Prime Contract No. ________________________
            Task No. _____________ Report No. ________________
           Subcontractor,             Subcontract Tier _______________
           Joint Effort
            (NASA prime contractor and NASA in-house)
           Multiple Contractor Contribution
           (collaboration of prime contractor and subcontractor)
           Other (e.g., Space Act or Cooperative Agreement)
           No. ______________________________________
UPN(s) ____________________
UPN(s) ____________________
UPN(s) ____________________
UPN(s) ____________________
UPN(s) ____________________
UPN(s) ____________________
UPN(s) ____________________ 

Contractor Reportable Item No.     ____________________

  1. NASA CONTRACTING OFFICER'S TECHNICAL REPRESENTATIVE (COTR)
NA
  1. CONTRACTOR/GRANTEE NEW TECHNOLOGY REPRESENTATIVE (POC)
NA
  1. BRIEF ABSTRACT (A general description of the innovation which describes its capabilities, but does not reveal details that would enable duplication or imitation of the innovation.)
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 similar products.)

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 (sns@ermapper.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:

Potential application users (who have contacted me expressing interest):
  • Pacific Meridian Resources, attn:  Tom Miewald, Portland, OR, phone:  503-228-8708, e-mail:   tmiewald@pacificmeridian.com .
  • Alpha Keita, Wuhan, Huazhong University of Science and Technology, Image Processing Institute, 430074, China (PRC), e-mail:   idak@public.wh.hb.cn .
  • Dr. Carolyn Evans, Department of Electronic Engineering, University of Reading, Whiteknights, Reading, RG6 6AY, United Kingdom, phone:   +44 (0) 118 9875 123 x7575, e-mail:   c.j.evans@reading.ac.uk .
  • Dr. Glenn Fitzgerald, USDA-ARS, 17053 N. Shafter Ave., Shafter, CA 93263, phone:   805-746-8009, e-mail:   ez003009@mailbox.ucdavis.edu .
  • Dr. Daniel L. Civco, Natural Resources Management & Engineering, Director, Laboratory for Earth Resources, U-87, Room 308, 1376 Storrs Road, The University of Connecticut, Storrs, CT 06269-4087, phone:  808-486-2840, e-mail:   dcivco@canr1.cag.uconn.edu .
Current user:
  • Dr. William T. Lawrence, Natural Sciences, Bowie State University, Bowie, MD 20715, phone:  301-464-6121, e-mail:   blawrenc@cs.bowiestate.edu .
NASA FORM 1679 JUL 98 REPLACES NF 425, NF 666, AND NF 666A, WHICH ARE OBSOLETE.                                     Page 3 of 4
  1. ADDITIONAL DOCUMENTATION (Include copies or list below any pertinent documentation which aids in the understanding or application of the innovation (e.g., articles, contractor reports, engineering specs, assembly/manufacturing drawings, parts or ingredients list, operating manuals, test data, assembly/manufacturing procedures, etc.).)
TITLE                  PAGE                               DATE

(See Section 15 below)

  1. DEGREE OF TECHNOLOGY SIGNIFICANCE (Which best expresses the degree of technological significance of this innovation?)

Modification to Existing Technology      X Substantial Advancement in the Art            Major Breakthrough

  1. STATE OF DEVELOPMENT

Concept Only         Design        X  Prototype         Modification         Production Model       X  Used in Current Work 

  1. PATENT STATUS (Prior patent on/or related to this innovation.)

Application Filed               Application No.                          Application Date
Patent Issued                        Patent No.                                    Issue Date 

  1. INDICATE THE DATE OR THE APPROXIMATE TIME PERIOD WHICH THIS INNOVATION WAS DEVELOPED (i.e., conceived, constructed, tested, etc.)
Development started in mid-1996, and continued through September 1999.
  1. PREVIOUS OR CONTEMPLATED PUBLICATION OR PUBLIC DISCLOSURE INCLUDING DATES (Provide as applicable: A. - Type of publication or disclosure, e.g., report, conference or seminar, oral presentation; B. - Disclosure by NASA or Contractor/Grantee; and C. - Title, volume no., page no., and date of publication.)

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:

James C. Tilton and William T. Lawrence, "Interactive Analysis of Hierarchical Segmentation," to be published in the Proceedings of the International Geoscience and Remote Sensing Symposium (IGARSS'00).

  1. QUESTIONS FOR SOFTWARE ONLY
(a.) Using outsiders to beta-test code?  _   YES  X  NO    If Yes, done under beta-test agreement? _ YES _ NO
(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 blawrenc@cs.bowiestate.edu.
(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: _______________
  1. DEVELOPMENT HISTORY
STAGE OF DEVELOPMENT
DATE (M/Y)
LOCATION
IDENTIFY SUPPORTING WITNESSES (NASA in-house only)
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 each innovator)

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.

  1. SIGNATURE(S) OF INNOVATOR(S), WITNESS(ES), AND NASA APPROVAL
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
APPROVED
TYPED
NAME 
SIGNATURE DATE
NASA FORM 1679 JUL 98 REPLACES NF 425, NF 666, AND NF 666A, WHICH ARE OBSOLETE.                                     Page 4 of 4