TEXT VERSION

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.

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

  1. DESCRIPTIVE TITLE
Method for Recursive Hierarchical Segmentation by Region Growing and Spectral Clustering with a Natural Convergence Criterion
  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.)
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

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

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:

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

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       Substantial Advancement in the Art            X 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.)
Initial development started in November 1997, and development continued steadily through January 2000.
  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.)

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:

J. C. Tilton, "Image segmentation by region growing and spectral clustering with a natural convergence criterion," Proc. of the 1998 International Geoscience and Remote Sensing Symposium, Seattle, WA, July 6-10, 1998.

J. C. Tilton, "A recursive PVM implementation of an image segmentation algorithm with performance comparisons in-between the HIVE and the Cray T3E," Proc. of the Seventh Symposium on the Frontiers of Massively Parallel Computation (Frontiers '99), Annapolis, MD, pp. 146-153, Feb. 21-25, 1999.

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:

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

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.

  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?  _   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: _______________
  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) 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.

  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