System and method for hierarchical segmentation with latent semantic indexing in scale space

• US 7,137,062 B2
• Filed: 12/28/2001
• Issued: 11/14/2006
• Est. Priority Date: 12/28/2001
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Slaney, Malcolm, Kaufman, James H., Ponceleon, Dulce Beatriz
• Primary Examiner(s): Hong, Stephen
• Assistant Examiner(s): STORK, KYLE R
• Application Number:
  US10/034,523
• Publication Number:
  US 20040205461A1
• Time in Patent Office: 1,782 Days
• Field of Search: 735/97, 704/207, 367/100, 367/127, 708/813, 715/512, 715/723, 715/500, 715/513, 715/517, 715/523, 715/530, 345/614, 707/101, 725/22
• US Class Current: 715/200
• CPC Class Codes: G06F 40/258 Heading extraction; Automatic titling; Numbering

Abstract

A system and method for automatically generating a hierarchical table of contents or outline for indexing a document and identifying clusters of related information in the document. The document may comprise text, audio, video, or a multimedia presentation. The invention employs a unique and novel combination of latent semantic indexing techniques to identify related blocks and major topic changes within the document with scale space segmentation techniques to respectively identify self-similar blocks within the document and to thus find topic changes of various sizes at block edges. The invention then produces a visual presentation of the semantic structure of the document.

Claims

1. A computer-implemented method for generating a table of contents for a document using information in said document, comprising:

building a model of said document including an initial semantic structure;

detecting hierarchical changes in said semantic structure spanning different scales by

applying successively smaller scale filter windows to said model according to said initial semantic structure to construct a map of said changes versus scale;

identifying local peaks in said contour map, said peaks being points of maximum vector derivative magnitude;

tracing said local peaks back to a semantic structure change origin point;

measuring a span of scales over which each said change exists; and

ordering said changes into entries in said table of contents based on scale span.

2. The method of claim 1 wherein said building further comprises:

defining a vector of terms occurring in said document; and

mapping said document into a vector space by projecting scaled term occurrence histogram data onto said vector of terms and summarizing said terms using singular-value decomposition.

3. A system for generating a table of contents for a document using information in said document, comprising:

means for building a model of said document including an initial semantic structure;

means for detecting hierarchical changes in said semantic structure spanning different scales by

applying successively smaller scale filter windows to said model according to said initial semantic structure to construct a map of said changes versus scale;

identifying local peaks in said contour map, said peaks being points of maximum vector derivative magnitude;

tracing said local peaks back to a semantic structure change origin point;

measuring a span of scales over which each said change exists; and

means for ordering said changes into entries in said table of contents based on scale span.

4. A computer program product comprising a machine-readable medium tangibly embodying computer-executable program instructions thereon for generating a table of contents for a document using information in said document, including:

a first code means for building a model of said document including an initial semantic structure;

a second code means for detecting hierarchical changes in said semantic structure spanning different scales by

applying successively smaller scale filter windows to said model according to said initial semantic structure to construct a map of said changes versus scale;

identifying local peaks in said contour map, said peaks being points of maximum vector derivative magnitude;

tracing said local peaks back to a semantic structure change origin point;

measuring a span of scales over which each said change exists; and

a third code means for ordering said changes into entries in said table of contents based on scale span.