Patent US6562077B2 successfully refreshed from Google Patents.
US6562077B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Sorting image segments into clusters based on a distance measurement
Assignee: Xerox Corp
•
Filing: 1997-11-14
•
Granted: 2003-05-13
•
Expires: 2017-11-14
Abstract
Abstract A programming interface of document search system enables a user to dynamically specifying features of documents recorded in a corpus of documents. The programming interface provides category and format flexibility for defining different genre of documents. The document search system initially segments document images into one or more layout objects. Each layout object identifies a structural element in a document such as text blocks, graphics, or halftones. Subsequently, the document search system computes a set of attributes for each of the identified layout objects. The set of attributes are used to describe the layout structure of a page image of a document in terms of the spatial relations that layout objects have to frames of reference that are defined by other layout objects. Using the set of attributes a user defines features of a document with the programming interface. After receiving a feature or attribute and a set of document images selected by a user, the system forms a set of image segments by identifying those layout objects in the set of document images that make up the selected feature or attribute. The system then sorts the set of image segments into meaningful groupings of objects which have similarities and/or recurring patterns. Subsequently, document images in the set of document images are ordered and displayed to a user in accordance with the meaningful groupings.
Inventors
- 👤 Daniel G. Bobrow
- 👤 James V. Mahoney
- 👤 William J. Rucklidge
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 20:52
CPC Classifications
G; G06; G06V; G06V30/00; G06V30/40; G06V30/41; G06V30/418; G06F; G06F16/00; G06F16/90; G06F16/93; G06V30/414
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
198 words
A method for sorting document images stored in a memory of a document management system, comprising the steps of: segmenting each document image recorded in the memory into a set of layout objects; each layout object in each of the sets of layout objects being one of a plurality of layout object types; each of the plurality of layout object types identifying a structural element of a document; selecting a feature of a document from a set of features; each of the features in the set of features identifying groups of layout objects in different ones of the sets of layout objects recorded in the memory; assembling in the memory a set of image segments; each image segment in the set of image segments identifying those layout objects of a document image stored in the memory that form the selected feature; computing a distance measurement between a selected image segment and ones of the image segments in the assembled set of image segments; and sorting the assembled set of image segments into clusters in the memory with the computed distance measurements; each cluster defining a grouping of image segments that have similar layout objects forming the selected feature.
Claim 2
Independent Claim
198 words
A method for sorting document images stored in a memory of a document management system, comprising the steps of: segmenting each document image recorded in the memory into a set of layout objects; each layout object in each of the sets of layout objects being one of a plurality of layout object types; each of the plurality of layout object types identifying a structural element of a document; selecting a feature of a document from a set of features; each of the features in the set of features identifying groups of layout objects in different ones of the sets of layout objects recorded in the memory; assembling in the memory a set of image segments; each image segment in the set of image segments identifying those layout objects of a document image stored in the memory that form the selected feature; computing a distance measurement between a selected image segment and ones of the image segments in the assembled set of image segments; and sorting the assembled set of image segments into clusters in the memory with the computed distance measurements; each cluster defining a grouping of image segments that have similar layout objects forming the selected feature.
Claim 3
Dependent Claim
21 words
The method according to claim 1 , wherein said selecting step selects a plurality of features from the set of features.
Claim 4
Dependent Claim
22 words
The method according to claim 1 , further comprising the step of selecting a subset of document images recorded in the memory.
Claim 5
Dependent Claim
33 words
The method according to claim 3 , wherein said assembling step assembles the set of image segments by identifying those layout objects of each document image in the selected subset of document images.
Claim 6
Dependent Claim
75 words
The method according to claim 1 , further comprises the steps of: selecting a first image segment from the set of image segment to define the selected image segment; computing a distance measurement between the first image segment and image segments remaining in the set of image segments; and defining a first cluster with the first image segment and certain of the remaining image segments having a distance measurement that is within a threshold distance.
Claim 7
Dependent Claim
91 words
The method according to claim 1 , further comprising the steps of: selecting a document image from the memory; assembling a single image segment to define the selected image segment by identifying those layout objects of the selected document image that form the selected feature; computing a distance measurement between the single image segment and each image segment in the set of image segments; and forming clusters of document images by ranking the computed distance measurement between the single image segment and each image segment in the set of image segments.
Claim 8
Dependent Claim
25 words
The method according to claim 1 , further comprising the step of displaying the assembled image segments in the clusters sorted by said sorting step.
Claim 9
Dependent Claim
53 words
The method according to claim 1 , further comprising the step of computing attributes for each layout object in the set of layout objects; the computed attributes of each layout object having values that quantify properties of a structural element and identify spatial relationships with other segmented layout objects in the document image.
Claim 10
Dependent Claim
66 words
The method according to claim 8 , further comprising the step of executing a routine for identifying a feature of the document image; the routine having a sequence of selection operations that consumes the set of layout objects and uses the computed attributes to produce a subset of layout objects; said executing step identifying the subset of layout objects as the feature of the document image.
Claim 11
Dependent Claim
44 words
The method according to claim 1 , further comprising the step of defining a structural model for identifying a genre of document; wherein the structural model defines a class of document images which express a common communicative purpose that is independent of document content.
Claim 12
Dependent Claim
20 words
The method according to claim 1 , further comprising the step of providing a user interface for selecting the feature.
Claim 13
Dependent Claim
30 words
The method according to claim 1 , wherein said assembling step assembles more than one layout object to form the selected feature of a document image stored in the memory.
Claim 14
Dependent Claim
65 words
The method according to claim 1 , further comprising the steps of: specifying a set of features in addition to the selected feature; wherein said sorting step assembles the set of image segments into clusters that include the selected feature and the specified set of features; and wherein the selected feature includes a subset of layout objects of ones of the specified set of features.
Claim 15
Dependent Claim
218 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for sorting document images stored in a memory of a document management system, said method steps comprising: segmenting each document image recorded in the memory into a set of layout objects; each layout object in each of the sets of layout objects being one of a plurality of layout object types; each of the plurality of layout object types identifying a structural element of a document; selecting a feature of a document from a set of features; each of the features in the set of features identifying groups of layout objects in different ones of the sets of layout objects recorded in the memory; assembling in the memory a set of image segments; each image segment in the set of image segments identifying those layout objects of a document image stored in the memory that form the selected feature; computing a distance measurement between a selected image segment and ones of the image segments in the assembled set of image segments; and sorting the assembled set of image segments into clusters in the memory with the computed distance measurements; each cluster defining a grouping of image segments that have similar layout objects forming the selected feature.
Claim 16
Dependent Claim
218 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for sorting document images stored in a memory of a document management system, said method steps comprising: segmenting each document image recorded in the memory into a set of layout objects; each layout object in each of the sets of layout objects being one of a plurality of layout object types; each of the plurality of layout object types identifying a structural element of a document; selecting a feature of a document from a set of features; each of the features in the set of features identifying groups of layout objects in different ones of the sets of layout objects recorded in the memory; assembling in the memory a set of image segments; each image segment in the set of image segments identifying those layout objects of a document image stored in the memory that form the selected feature; computing a distance measurement between a selected image segment and ones of the image segments in the assembled set of image segments; and sorting the assembled set of image segments into clusters in the memory with the computed distance measurements; each cluster defining a grouping of image segments that have similar layout objects forming the selected feature.
Claim 17
Dependent Claim
82 words
The program storage device as recited in claim 14 , wherein said method steps further comprises the steps of: selecting a first image segment from the set of image segment to define the selected image segment; computing a distance measurement between the first image segment and image segments remaining in the set of image segments; and defining a first cluster with the first image segment and certain of the remaining image segments having a distance measurement that is within a threshold distance.
Claim 18
Dependent Claim
98 words
The program storage device as recited in claim 14 , wherein said method steps further comprises the steps of: selecting a document image from the memory; assembling a single image segment to define the selected image segment by identifying those layout objects of the selected document image that form the selected feature; computing a distance measurement between the single image segment and each image segment in the set of image segments; and forming clusters of document images by ranking the computed distance measurement between the single image segment and each image segment in the set of image segments.
Claim 19
Dependent Claim
72 words
The program storage device as recited in claim 14 , wherein said method steps further comprise the step of: specifying a set of features in addition to the selected feature; wherein said sorting step assembles the set of image segments into clusters that include the selected feature and the specified set of features; and wherein the selected feature includes a subset of layout objects of ones of the specified set of features.
Claim 20
Dependent Claim
230 words
A document management system for sorting document images, comprising: a memory for storing the document images and image processing instructions of the document management system; and a processor coupled to the memory for executing the image processing instructions of the document management system; the processor in executing the image processing instructions: segmenting each document image recorded in the memory into a set of layout objects; each layout object in each of the sets of layout objects being one of a plurality of layout object types; each of the plurality of layout object types identifying a structural element of a document; selecting a feature of a document from a set of features; each of the features in the set of features identifying groups of layout objects in different ones of the sets of layout objects recorded in the memory; assembling in the memory a set of image segments; each image segment in the set of image segments identifying those layout objects of a document image stored in the memory that form the selected feature; computing a distance measurement between a selected image segment and ones of the image segments in the assembled set of image segments; and sorting the assembled set of image segments into clusters in the memory with the computed distance measurements; each cluster defining a grouping of image segments that have similar layout objects forming the selected feature.
Claim 21
Dependent Claim
230 words
A document management system for sorting document images, comprising: a memory for storing the document images and image processing instructions of the document management system; and a processor coupled to the memory for executing the image processing instructions of the document management system; the processor in executing the image processing instructions: segmenting each document image recorded in the memory into a set of layout objects; each layout object in each of the sets of layout objects being one of a plurality of layout object types; each of the plurality of layout object types identifying a structural element of a document; selecting a feature of a document from a set of features; each of the features in the set of features identifying groups of layout objects in different ones of the sets of layout objects recorded in the memory; assembling in the memory a set of image segments; each image segment in the set of image segments identifying those layout objects of a document image stored in the memory that form the selected feature; computing a distance measurement between a selected image segment and ones of the image segments in the assembled set of image segments; and sorting the assembled set of image segments into clusters in the memory with the computed distance measurements; each cluster defining a grouping of image segments that have similar layout objects forming the selected feature.
Claim 22
Dependent Claim
18 words
The document management system according to claim 18 , further comprising a program interface for selecting the feature.
Claim 23
Dependent Claim
29 words
The document management system according to claim 18 , wherein said program interface provides means for selecting a first feature and a second feature from the set of features.
Claim 24
Dependent Claim
23 words
The document management system according to claim 18 , further comprising means for selecting a set of document images recorded in the memory.
Claim 25
Dependent Claim
34 words
The document management system according to claim 21 , wherein said selecting assembles a set of image segments by identifying those layout objects of each document image in the selected set of document images.
Claim 26
Dependent Claim
74 words
The document management system according to claim 18 , wherein the processor in executing the image processing instructions: specifies a set of features in addition to the selected feature; and wherein said sorting image processing instruction assembles the set of image segments into clusters that include the selected feature and the specified set of features; and wherein the selected feature includes a subset of layout objects of ones of the specified set of features.
References Cited (Backward Citations)
JPS59103460A
Cited
US4574395A
Cited
US4908873A
Cited
US4632252A
Cited
US4783825A
Cited
US5265242A
Cited
US4912771A
Cited
US4845761A
Cited
US5084769A
Cited
US5228100A
Cited
US5313572A
Cited
US5060980A
Cited
US5363214A
Cited
US5625770A
Cited
US5442778A
Cited
EP0544431A2
Cited
US5384863A
Cited
US5321770A
Cited
US5325444A
Cited
EP0544432A2
Cited
US5491760A
Cited
US5390259A
Cited
US5369714A
Cited
US5434953A
Cited
US5448375A
Cited
US5282052A
Cited
US5267303A
Cited
US5317646A
Cited
US5335088A
Cited
US5339172A
Cited
US5542002A
Cited
US5859935A
Cited
US5745610A
Cited
US6173275B1
Cited
US5434933A
Cited
US5455898A
Cited
US5537491A
Cited
US5539841A
Cited
US5850490A
Cited
US5930809A
Cited
US5724579A
Cited
US5857199A
Cited
US5524066A
Cited
US5598507A
Cited
US5966455A
Cited
US6052481A
Cited
US5694594A
Cited
US5953732A
Cited
US5909508A
Cited
US5708825A
Cited
US5764799A
Cited
US5778397A
Cited
US6009196A
Cited
US5889886A
Cited
US5818965A
Cited
US5999653A
Cited
US5931907A
Cited
US5835638A
Cited
US6038561A
Cited
US6038340A
Cited
US6327387B1
Cited
US6058205A
Cited
US6108446A
Cited
US6137911A
Cited
EP0889417A2
Cited
US6128410A
Cited
US6014452A
Cited
US5930393A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-05-12 | 2006-11-11 | 2007-05-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-05-12 | 2010-11-11 | 2011-05-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-05-12 | 2014-11-11 | 2015-05-13 | $7700.00 | Window Closed / Lapsed |