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.
National Aeronautics and Space Administration | Disclosure of Invention and New Technology (Including Software) |
O.M.B. NO. 2700-0009 |
DATE
02/28/00 |
|||||||||
NT CONTROL NO. (OFFICIAL USE ONLY)
NASA Case No. GSC 14,328-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. |
||||||||||||
Method for Recursive
Hierarchical Segmentation by Region Growing and Spectral Clustering
with a Natural Convergence Criterion
|
||||||||||||
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 _______________ 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. ____________________ |
||||||||||
NA
|
NA
|
|||||||||||
The innovation disclosed herein
is a method for hierarchical segmentation algorithm (referred to as
HSEG) and its recursive formulation (referred to as RHSEG). The
HSEG algorithm is a hybrid of region growing and spectral
clustering that produces a hierarchical set of image segmentations
based on detected natural convergence points. This algorithm is
very computationally intensive. An efficient recursive,
divide-and-conquer, implementation of HSEG has been devised. This
recursive form of the algorithm is more computationally efficient
than a non-recursive form. An implementation of RHSEG on parallel
computers is the subject of a patent application under NASA Case
No. GSC 14,305-1. However, the serial implementation is public
domain and is fully disclosed herein.
|
||||||||||||
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 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 |
||||||||||||
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: D. - Alternate embodiments of the innovation/software: (described in prior art section - I.C.) 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. |
||||||||||||
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:
B. - Advantages of innovation/software:
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: |
||||||||||||
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:
|
||||||||||||
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 Substantial Advancement in the Art X Major Breakthrough |
||||||||||||
Concept Only Design X Prototype Modification Production Model X Used in Current Work |
||||||||||||
Application
Filed
Application
No.
Application Date |
||||||||||||
Initial development started in
November 1997, and development continued steadily through January
2000.
|
||||||||||||
General outlines of the hierarchical segmentation algorithm (HSEG) and the recursive hierarchical segmentation algorithm (RHSEG) were previously disclosed in two papers that were published in symposium proceedings: In addition, an early version of the recursive implementation of HSEG was discussed in informal meetings with individuals from Cambridge Parallel Processing (CPP) in late February 1999. Related technical discussions continued through mid-May 1999 via e-mail and telephone with Dr. Stewart Reddaway, Cambridge Parallel Processing, Centennial Court, Easthampstead Road, Bracknell, Berks RG12 1YQ, United Kingdom (e-mail sfr@cppuk.co.uk). The discussions with Dr. Reddaway centered around the possibility of implementing the HSEG algorithm on CPP's Gamma II Plus 4096 processor SIMD (single instruction multiple data streams) parallel computer. The result of these discussion was included in a white paper to NASA's Earth Science Enterprise: Ongoing collaborative research 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: Notwithstanding these previous disclosures, many important technical details concerning the HSEG and RHSEG algorithms were not disclosed in the above discussions, white paper or symposium proceedings and have not been previously disclosed. |
||||||||||||
|
||||||||||||
(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? _ YES X NO If Yes, supply NASA or Contractor contact: __________________ (e.) Contains or is based on code owned by a non-federal entity? _ YES X NO _ UNKNOWN If Yes, has a license for use been obtained? _ 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) | 10/99 | NASA's GSFC | ||||||||||
e. First successful operational test (invention) or alpha version (software) | 01/00 | NASA's GSFC | ||||||||||
f. Contribution of
innovators (if jointly developed, provide the contribution of
each innovator)
Developed exclusively by James C. Tilton, Code 935 (Applied Information Science's Branch), NASA's Goddard Space Flight Center, Greenbelt, MD USA 20771. |
||||||||||||
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 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 |