US 5,668,897 AGranted

Method and apparatus for imaging, image processing and data compression merge/purge techniques for document image databases

OwnerSalvatore J. Stolfoinventor

Life of this patent

Estimating the term…

Loading patent…

Abstract

A method for processing an image, consisting of a foreground and a background, to produce a highly compressed and accurate representation of the image, including the steps of scanning the image to create a digital image of the image, comparing the digital image against a codebook of stored digital images; matching the digital image with one of the stored digital images of the codebook; producing an index code identifying the background of the stored digital image as having matched the digital image; subtracting the stored digital image from the digital image to produce a second digital image representing the foreground of the stored digital image; and storing the second digital image with the index code. Techniques are also provided to enable merge/purge of the database(s) thereby created.

Claims18

Dependent claims

A method for processing at least two images and storing the images in a database, comprising the steps of:

(a) scanning the image to create a first digital image thereof;
(b) comparing said first digital image against a codebook of stored digital images;
(c) matching said first digital image with one of said stored digital images;
(d) producing an index code identifying said one of said stored digital images as having matched said first digital image;
(e) subtracting said one of said stored digital images from said first digital image to produce a second digital image;
(f) storing said second digital image together with its respective index code as a record in the database;
(g) repeating steps (a) through (g) at least once for another image;
(h) clustering said stored images with their respective index codes based upon the use of at least one key, wherein said at least, one key comprises a first key and second key;
(i) computing said first key for each record in the database by extracting at least a portion of a first field;
(j) merge sorting the records in the database using said first key;
(k) comparing to each other a predetermined number of sequential reports sorted according to said first key to determine if one or more of the records match;
(l) storing identifiers for any matching records;
(m) computing said second key for each record in the database by extracting at least a portion of a second field;
(n) merge sorting the records in the database using said second key;
(o) comparing to each other a predetermined number of sequential records sorted according to said second key to determine if one or more of the records match;
(p) storing identifiers for any matching records;
(q) creating union of said stored identifiers;
and
(r) subjecting said union to transitive closure.

16 more elements

A method for processing at least two images, storing the images in a database, and creating a codebook representing portions of at least one of said images, comprising the steps of:

(a) scanning each image to create a first digital image thereof;
(b) storing each scanned image as a record in a database;
(c) computing a first key for each record in the database by extracting at least a portion of a scanned image to create a field image;
(d) merge sorting the records in the database using the first key;
(e) comparing to each other a predetermined number of sequential records sorted according to the first key to determine if another record has a field image that matches the field image;
(f) creating an identifier specific for each such matching field image that identifies the particular record in which the match was found;
(g) subtracting the matched field image from the identified record to produce a residual image;
(h) storing the residual image with its specific identifier;
(i) storing the subtracted, matched field image in a codebook database;
(j) computing a second key for each record in the database by extracting at least a portion of a scanned image to create a second field image;
(k) merge sorting the records in the database using the second key:
(l) comparing to each other a predetermined number of sequential records sorted according to the second key to determine if a record has a field image that matches the second field image;
(m) storing an identifier specific for each such matching second field image that identifies the particular record in which the match was found;
(n) subtracting the matched second field image from the identified record;
and
(o) storing the matched second field image in a codebook database.

13 more elements

A method for processing at least two images, storing the image in database, and creating a codebook representing portions of at least one of said images, comprising the steps of:

(a) scanning each image to create a first digital image thereof;
(b) storing each scanned image as a record in a database;
(c) computing a first key for each record in the database by extracting at least a portion of a scanned image to create a field image;
(d) merge sorting the records in the database using the first key;
(e) comparing to each other a predetermined number of sequential records sorted according to the first key to determine if another record has a field image that matches the field image;
(f) creating an identifier specific for each such matching field image that identifies the particular record in which the match was found;
(g) subtracting the matched field image from the identified record to produce a residual image;
(h) storing the residual image with its specific identifier;
(i) storing the subtracted, matched field image in a codebook datebase;
(j) computing a second key for each residual image in the database by extracting at least a portion thereof to create a second field image;
(k) merge sorting the residual images in the database using the second key;
(l) comparing to each other a predetermined number of sequential residual images sorted according to the second key to determine if a residual image has a field image that matches the second field image;
(m) creating an identifier specific for each such matching second field image that identifies the particular residual image in which the match was found;
(n) subtracting the matched second field image from the respective residual image;
(o) storing the residual image with its specific identifier;
and
(p) storing the subtracted, matched second field image in a codebook database.

14 more elements

Dependencies are inferred from the claim text.

Facts

Application: 08/488,333Filed 7 Jun 1995 · continuation in part
Priority: 15 Mar 1994
Granted: 16 Sep 1997
Term ends: Not estimatedThe source records don’t support an estimate.

Classification6 codes

G06F 16/583
Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually: using metadata automatically…
G06F 16/284
Databases characterised by their database models, e.g. relational or object models: relational databases
G06F 16/5838
Using metadata automatically derived from the content: using colour
G06V 2201/01
Indexing scheme relating to image or video recognition or understanding: solutions for problems related to non-uniform document background

Family

Serial213,795Parent of this continuation-in-part · filed 15 Mar 1994
Serial224,273Parent of this continuation-in-part · filed 7 Apr 1994
Serial259,527Parent of this continuation-in-part · filed 14 Jun 1994
US 5,497,486 AParent of this continuation-in-part
US 5,668,897 AThis patent

From the US filing history. Foreign family members aren’t listed.