NASA Case No. GSC 14,328-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

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

D. - Disadvantages or limitation of prior art.

REFERENCES

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:

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: (described in prior art section - I.C.)

E. - Supportive theory:

F. - Engineering specifications: Not applicable.

G. - Peripheral equipment

The software described herein 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.

REFERENCES

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:

1. A region growing approach to image segmentation is combined with spectral clustering to form a hybrid image segmentation algorithm.
2. This hybrid image segmentation algorithm is approximated by a recursive, divide-and-conquer approach that greatly reduces processing time.
3. I am aware of only two other instances in the technical literature of using the "step-wise optimal" approach:  Beaulieu and Goldberg [1] (and Beaulieu [2]) and Haris, et al, [3].  However, Haris, et al, recommend against initializing the step-wise optimal approach with individual pixel regions, which is my approach.
4. Most other image segmentation approaches output a single image segmentation.  However, this approach outputs a hierarchical set of image segmentations for single-band, multispectral (multiband) or hyperspectral image data.  The hierarchical set of image segmentations those segmentations that occur just prior to significant changes in an overall dissimilarity function.  An interactive software tool (see, for example, the "Region Labeling Tool" described at http://code935.gsfc.nasa.gov/code935/tilton/index.html#REGLBL_TOOL and in NASA Case No. 14,331-1) 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:

1. The hybridization of region growing and spectral clustering makes possible the combination of spectrally similar but spatially disjoint regions while maintaining the robustness of the region growing approach.
2. It is generally difficult to determine at what point to terminate region growing (where the process converges) in most region growing approaches.  The hierarchical set of segmentations produced by this approach eliminates the need to determine a single convergence point.  In addition, a single set of hierarchical segmentations can be used to determine the appropriate single segmentation for a wide range of applications using an interactive region labeling tool.  Utilizing human interaction at this point takes the greatest advantage of human 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:  There is no re-use or re-engineering of existing code, use of shareware, or use of code owned by a non-federal entity.  However, there does exist an optional graphical user interface (GUI) program which utilizes the commercial Khoros Pro 2000 software package.  This optional GUI program is not part of this disclosure.  The optional GUI program provides a convenient user-friendly way to create the input parameter file for the HSEG and RHSEG programs and convert data file to and from Khoros data object format.  Since the input parameter file can be created manually, and the data files can be formatted manually, the GUI program is not necessary for running the programs.

REFERENCES:
[1] J.-M. Beaulieu and M. Goldberg, "Hierarchy in picture segmentation:  A stepwise optimization approach," IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 11, No. 2, pp. 150-163, Feb. 1989.
[2] J.-M. Beaulieu, "Versatile and efficient hierarchical clustering for picture segmentation,"  Proc. of the 10th Annual International Geoscience and Remote Sensing Symposium (IGARSS'90), College Park, MD, p. 1663, May 20-24, 1990.
[3] K. Haris, S. N. Efstratiadis, N. Maglaveras and A. K. Katsaggelos, "Hybrid image segmentation using watersheds and fast region merging," IEEE Transactions on Image Processing, Vol. 7, No. 12, pp. 1684-1699, December 1998.
 

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 at http://code935.gsfc.nasa.gov/code935/tilton/ index.html#REGLBL_TOOL) 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 the information at http://code935.gsfc.nasa.gov/code935/tilton/index.html.  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 HSEG and RHSEG programs 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.

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