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.

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

2. 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.

3. EMPLOYER(S) WHEN INNOVATION MADE (Name and Division)

4. ADDRESS(ES) (Place of performance)

5. EMPLOYER STATUS

6. ORIGIN

7. NASA CONTRACTING OFFICER'S TECHNICAL REPRESENTATIVE (COTR)

8. CONTRACTOR/GRANTEE NEW TECHNOLOGY REPRESENTATIVE (POC)

9. 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.)

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.

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)

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, 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:

• ER Mapper:   http://www.ermapper.com or queries@ermapper.com or ER Mapper, 4370 La Jolla Village Drive, Suite 900, San Diego, CA 92122-1235, USA; Tel. +1 858 558-4709; Fax. +1 858 558-2657.
• Research Systems, Inc (ENVI):   http://www.rsinc.com or info@rsinc.com or Research Systems, Inc., 4990 Pearl East Circle, Boulder, CO 80301; tel:  303-786-9900; fax:  303-786-9909.
• ERDAS, Inc.:   http://www.erdas.com or ERDAS, Inc., 2801 Buford Highway, Atlanta, Georgia U.S.A. 30329-2137; Phone:  404-248-9000; Fax:  404-248-9400.
• ESRI (ArcInfo and ArcView GIS):   http://www.esri.com or info@esri.com or ESRI, 380 New York Street, Redlands, CA 92373-8100 USA; Phone:   909-793-2853; FAX:   909-793-5953.
• Intergraph Corporation (Image Analyst or Earth View APP): http://www.intergraph.com/photogrammetry or info@intergraph.com or Intergraph Corporation, Huntsville, Alabama 35894-0001; Phone:  1-800-345-4856.
• Clark Labs (IDRISI):  http://www.idrisi.com or idrisi@clarku.edu or Clark Labs, Clark University, 950 Main Street, Worcester, MA; Tel:  508-793-7526; FAX:   508-793-8842.
• ThinkSpace Inc. (MFworks for Remote Sensing):  http://www.thinkspace.com or info@thinkspace.com or ThinkSpace, Inc., 1747 E. Northern Avenue, Suite 279, Phoenix, AZ 85020 USA
• Khoral Research, Inc.(Khoros Pro):   http://www.khoral.com or Khoral Research, Inc, 6200 Uptown Blvd., N.E., Suite 200, Albuquerque, New Mexico 87110; Tel. 505-881-3842.

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.

10. 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.).)

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

12. STATE OF DEVELOPMENT

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

14. INDICATE THE DATE OR THE APPROXIMATE TIME PERIOD WHICH THIS INNOVATION WAS DEVELOPED (i.e., conceived, constructed, tested, etc.)

15. 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.)

16. QUESTIONS FOR SOFTWARE ONLY

17. DEVELOPMENT HISTORY

18. SIGNATURE(S) OF INNOVATOR(S), WITNESS(ES), AND NASA APPROVAL