US5867597A
Expired / Lapsed
US
⏱️ 0.0 years remaining
High-speed retrieval by example
Assignee: Ricoh Co Ltd
•
Filing: 1995-09-05
•
Granted: 1999-02-02
•
Expires: 2015-09-05
Abstract
Abstract An improved document management system with high-speed retrieval by example retrieves a document attaching a target document, in whole or part, by comparing descriptors of documents. A descriptor is derived from a pattern of labels, where each label is associated with a character, or more precisely, a character bounding box. A bounding box is found by examining contiguous pixels in an image. The particular label associated with a bounding box depends on the value of a metric measured from that bounding box. In one system, the metric is the spacing between the bounding box and an adjacent bounding box, in which the labels approximately reflect a pattern of word lengths. In other systems, where words lengths are not present, the metric might be pixel density and the pattern of labels approximately reflect a pattern of denser characters and sparser characters. The document management system, or just the query portion of the document management system could be part of a copier, where a sample page is input to the copier and the copier retrieves the matching document and prints it.
Inventors
- 👤 Mark Peairs
- 👤 Jonathan Hull
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 22:06
CPC Classifications
G; G06; G06V; G06V30/00; G06V30/40; G06V30/41; G06V30/414; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99935; Y10S707/99936
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
200 words
A document retrieval apparatus, wherein a target document is input and a matching document is retrieved from a document database, comprising: character detecting means for detecting character bounds in the target document based on image content of the target document; discrimination means, coupled to the character detecting means, for discriminating the character bounds into classes, wherein discrimination is done based on at least one unambiguous characteristic of the character bound including the pixel density over an area of the character bound; descriptor generating means, coupled to receive class indications of character bounds from the character detecting means, for generating target document descriptors based on patterns of class indications; searching means, coupled to receive the target document descriptors from the descriptor generating means, for searching the document database for potentially matching documents which have descriptors in common with the target document; evaluation means, coupled to receive a set of potentially matching documents from the searching means, for determining at least one matching document from among the potentially matching documents; and output means, coupled to the evaluation means, for outputting the at least one matching document or indication thereof as a result of a retrieval request wherein the target document is input.
Claim 2
Dependent Claim
200 words
A document retrieval apparatus, wherein a target document is input and a matching document is retrieved from a document database, comprising: character detecting means for detecting character bounds in the target document based on image content of the target document; discrimination means, coupled to the character detecting means, for discriminating the character bounds into classes, wherein discrimination is done based on at least one unambiguous characteristic of the character bound including the pixel density over an area of the character bound; descriptor generating means, coupled to receive class indications of character bounds from the character detecting means, for generating target document descriptors based on patterns of class indications; searching means, coupled to receive the target document descriptors from the descriptor generating means, for searching the document database for potentially matching documents which have descriptors in common with the target document; evaluation means, coupled to receive a set of potentially matching documents from the searching means, for determining at least one matching document from among the potentially matching documents; and output means, coupled to the evaluation means, for outputting the at least one matching document or indication thereof as a result of a retrieval request wherein the target document is input.
Claim 3
Dependent Claim
19 words
The document retrieval apparatus of claim 1, wherein the at least one unambiguous characteristic includes spacing between character bounds.
Claim 4
Dependent Claim
17 words
The document retrieval apparatus of claim 1, wherein the characters of the target document are Japanese characters.
Claim 5
Dependent Claim
20 words
The document retrieval apparatus of claim 1, wherein the discriminating means discriminates each character bound into one of two classes.
Claim 6
Dependent Claim
31 words
The document retrieval apparatus of claim 4, wherein the two classes are the class of character bounds with pixel density less than a threshold and pixel density greater than the threshold.
Claim 7
Dependent Claim
17 words
The document retrieval apparatus of claim 1, wherein the target document is input as a paper document.
Claim 8
Dependent Claim
21 words
The document retrieval apparatus of claim 1, wherein the target document is input as an electronic image of the target document.
Claim 9
Independent Claim
222 words
A method of using a target document to specify a matching document in a document retrieval system which includes a document database in which the matching document is stored and the matching document is the target document or a document with elements in common with the target document, the method comprising the steps of: inputting an image of the target document to the document retrieval system; detecting character bounds in the target document image; measuring at least one metric for each character bound in a sample of the character bounds, thereby resulting in a distribution of metric values, the at least one metric including a pixel density over an area of the character bound; dividing the distribution of metric values into a plurality of ranges where each range is associated with one class of character bounds; labelling each character bound in the sample with an indication of its class based on the metric value for said each character bound; forming descriptors for the target document based on patterns of class indications; searching an index of descriptors for documents in the document database using the formed descriptors of the target document; identifying at least one document in the document database as a matching document when the at least one document has more descriptors in common with the target document than a nonmatching document.
Claim 10
Independent Claim
222 words
A method of using a target document to specify a matching document in a document retrieval system which includes a document database in which the matching document is stored and the matching document is the target document or a document with elements in common with the target document, the method comprising the steps of: inputting an image of the target document to the document retrieval system; detecting character bounds in the target document image; measuring at least one metric for each character bound in a sample of the character bounds, thereby resulting in a distribution of metric values, the at least one metric including a pixel density over an area of the character bound; dividing the distribution of metric values into a plurality of ranges where each range is associated with one class of character bounds; labelling each character bound in the sample with an indication of its class based on the metric value for said each character bound; forming descriptors for the target document based on patterns of class indications; searching an index of descriptors for documents in the document database using the formed descriptors of the target document; identifying at least one document in the document database as a matching document when the at least one document has more descriptors in common with the target document than a nonmatching document.
Claim 11
Dependent Claim
22 words
The method of claim 8, wherein the plurality of ranges of metric values is two ranges separated by the threshold metric value.
Claim 12
Independent Claim
176 words
An apparatus for matching an input document to a reference document in a document database, comprising: a document database, wherein reference descriptors are derived from content of reference documents in said document database; a descriptor database associating reference descriptors and reference documents, wherein a reference descriptor describes, at least in part, a pattern of character densities and a specific reference descriptor and a specific reference document are associated in the descriptor database when the pattern of character densities described by the specific reference descriptor is found in the specific reference document; input means for inputting content of an input document to be matched against said reference documents of said document database; descriptor derivation means, coupled to said input means, for deriving at least one input descriptor from the input document where said input descriptor describes, at least in part, a pattern of character densities found in the input document; and output means, coupled to said descriptor derivation means, for outputting an indication of reference documents which are associated with reference descriptors which match the input descriptor.
Claim 13
Independent Claim
176 words
An apparatus for matching an input document to a reference document in a document database, comprising: a document database, wherein reference descriptors are derived from content of reference documents in said document database; a descriptor database associating reference descriptors and reference documents, wherein a reference descriptor describes, at least in part, a pattern of character densities and a specific reference descriptor and a specific reference document are associated in the descriptor database when the pattern of character densities described by the specific reference descriptor is found in the specific reference document; input means for inputting content of an input document to be matched against said reference documents of said document database; descriptor derivation means, coupled to said input means, for deriving at least one input descriptor from the input document where said input descriptor describes, at least in part, a pattern of character densities found in the input document; and output means, coupled to said descriptor derivation means, for outputting an indication of reference documents which are associated with reference descriptors which match the input descriptor.
Claim 14
Dependent Claim
26 words
The apparatus of claim 10, wherein the input documents and target documents are formatted as ASCII documents, page description language documents or word processing format documents.
Claim 15
Independent Claim
187 words
A method of using a target document to specify a matching document in a document retrieval system which includes a document database in which the matching document is stored and the matching document is the target document or a document with elements in common with the target document, the method comprising the steps of: inputting an image of the target document to the document retrieval system; detecting character features in the target document image according to a plurality of classes of character features, wherein at least one of the character features detected is a pixel density over an area of a character bound; forming descriptors for the target document based on the detected character features of each of the plurality of classes of character features; for each class of character features, searching an index of descriptors for documents in the document database using the formed descriptors of the target document for said each class; and identifying at least one document in the document database as a matching document when the at least one document has more descriptors in common with the target document than a nonmatching document.
Claim 16
Independent Claim
187 words
A method of using a target document to specify a matching document in a document retrieval system which includes a document database in which the matching document is stored and the matching document is the target document or a document with elements in common with the target document, the method comprising the steps of: inputting an image of the target document to the document retrieval system; detecting character features in the target document image according to a plurality of classes of character features, wherein at least one of the character features detected is a pixel density over an area of a character bound; forming descriptors for the target document based on the detected character features of each of the plurality of classes of character features; for each class of character features, searching an index of descriptors for documents in the document database using the formed descriptors of the target document for said each class; and identifying at least one document in the document database as a matching document when the at least one document has more descriptors in common with the target document than a nonmatching document.
Claim 17
Dependent Claim
51 words
The method of claim 12, wherein the plurality of classes of character features includes an intercharacter spacing class of features describing patterns of word lengths and a character pixel density class of features describing at least a binary pattern of character density being greater than or less than a threshold density.
Claim 18
Independent Claim
204 words
A method of using a target document to specify a matching document in a document retrieval system which includes a document database in which the matching document is stored and the matching document is the target document or a document with elements in common with the target document, the method comprising the steps of: inputting an image of the target document to the document retrieval system; detecting character features in the target document image according to a plurality of classes of character features; forming descriptors for the target document based on the detected character features of each of the plurality of classes of character features; for each class of character features, searching an index of descriptors for documents in the document database using the formed descriptors of the target document for said each class; and identifying at least one document in the document database as a matching document when the at least one document has more descriptors in common with the target document than a nonmatching document wherein the plurality of classes of character features includes a word length class of features describing patterns of word lengths and a phoneme word length class of features describing patterns of the number of phonemes per word.
Claim 19
Independent Claim
204 words
A method of using a target document to specify a matching document in a document retrieval system which includes a document database in which the matching document is stored and the matching document is the target document or a document with elements in common with the target document, the method comprising the steps of: inputting an image of the target document to the document retrieval system; detecting character features in the target document image according to a plurality of classes of character features; forming descriptors for the target document based on the detected character features of each of the plurality of classes of character features; for each class of character features, searching an index of descriptors for documents in the document database using the formed descriptors of the target document for said each class; and identifying at least one document in the document database as a matching document when the at least one document has more descriptors in common with the target document than a nonmatching document wherein the plurality of classes of character features includes a word length class of features describing patterns of word lengths and a phoneme word length class of features describing patterns of the number of phonemes per word.
Claim 20
Independent Claim
220 words
A method of using a target document to specify a matching document in a document retrieval system which includes a document database in which the matching document is stored and the matching document is the target document or a document with elements in common with the target document, the method comprising the steps of: inputting an image of the target document to the document retrieval system; detecting character features in the target document image according to a plurality of classes of character features; forming descriptors for the target document based on the detected character features of each of the plurality of classes of character features; for each class of character features, searching an index of descriptors for documents in the document database using the formed descriptors of the target document for said each class; and identifying at least one document in the document database as a matching document when the at least one document has more descriptors in common with the target document than a nonmatching document wherein the plurality of classes of character features includes an intercharacter spacing class of features describing patterns of word lengths, a character pixel density class of features describing a pattern of at least character densities compared with a threshold, and a phoneme spacing class of features describing the number of phonemes per word.
Claim 21
Independent Claim
220 words
A method of using a target document to specify a matching document in a document retrieval system which includes a document database in which the matching document is stored and the matching document is the target document or a document with elements in common with the target document, the method comprising the steps of: inputting an image of the target document to the document retrieval system; detecting character features in the target document image according to a plurality of classes of character features; forming descriptors for the target document based on the detected character features of each of the plurality of classes of character features; for each class of character features, searching an index of descriptors for documents in the document database using the formed descriptors of the target document for said each class; and identifying at least one document in the document database as a matching document when the at least one document has more descriptors in common with the target document than a nonmatching document wherein the plurality of classes of character features includes an intercharacter spacing class of features describing patterns of word lengths, a character pixel density class of features describing a pattern of at least character densities compared with a threshold, and a phoneme spacing class of features describing the number of phonemes per word.
Claim 22
Independent Claim
166 words
A method of using a target document to specify a matching document in a document retrieval system which includes a document database in which the matching document is stored and the matching document is the target document or a document with elements in common with the target document, the method comprising the steps of: inputting an image of the target document to the document retrieval system; detecting phoneme features in the target document image according to a plurality of classes of phoneme features; forming descriptors for the target document based on the detected phoneme features of each of the plurality of classes of phoneme features; for each class of phoneme features, searching an index of descriptors for documents in the document database using the formed descriptors of the target document for said each class; identifying at least one document in the document database as a matching document when the at least one document has more descriptors in common with the target document than a nonmatching document.
Claim 23
Independent Claim
166 words
A method of using a target document to specify a matching document in a document retrieval system which includes a document database in which the matching document is stored and the matching document is the target document or a document with elements in common with the target document, the method comprising the steps of: inputting an image of the target document to the document retrieval system; detecting phoneme features in the target document image according to a plurality of classes of phoneme features; forming descriptors for the target document based on the detected phoneme features of each of the plurality of classes of phoneme features; for each class of phoneme features, searching an index of descriptors for documents in the document database using the formed descriptors of the target document for said each class; identifying at least one document in the document database as a matching document when the at least one document has more descriptors in common with the target document than a nonmatching document.
Claim 24
Dependent Claim
18 words
The method of claim 16, wherein the phoneme features describe patterns of the number of phonemes per word.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-02-01 | 2002-08-03 | 2003-02-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-02-01 | 2006-08-03 | 2007-02-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-02-01 | 2010-08-03 | 2011-02-02 | $7700.00 | Window Closed / Lapsed |