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

• US 5,668,897 A
• Filed: 06/07/1995
• Issued: 09/16/1997
• Est. Priority Date: 03/15/1994
• Status: Expired due to Term

• Current Assignee: Lot 19 Acquisition Foundation LLC (Intellectual Ventures LLC)
• Original Assignee: Salvatore J. Stolfo
• Inventors: Stolfo, Salvatore J.
• Primary Examiner(s): Couso, Jose L.
• Application Number:
  US08/488,333
• Time in Patent Office: 832 Days
• Field of Search: 382/135, 382/137, 382/138, 382/139, 382/209, 382/218, 382/282, 382/232, 382/283, 382/317, 382/284, 358/435, 358/436
• US Class Current: 382/283
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06V 2201/01 Solutions for problems related to non-uniform document background

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.

Claims

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

2. The method of claim 1, where in the comparing steps are each performed on a separate processor.

3. The method of claim 2, wherein the database is sorted in parallel using parallel merge sorting.

4. The method of claim 3, wherein in each group of processors for each database:

(i) N is a number of records;

(ii) P is a number of processors, each processor p, 1≦

p≦

P, being able to store M+w records;

(a) w is a size of a merge phase window; and

(b) M is a blocking factor;

(ii) P is less than N;

(iii) r_i represents record i in a cluster, 0≦

i<

MP-1; and

(a) each said comparing step comprises the steps of;

(i) dividing the sorted database into N/MP clusters;

(ii) processing each of the N/MP clusters in turn by providing each processor p with records r.sub.(p-1)M, , , , r_pM-1, . . ., r_pM+w-2, for 1≦

p≦

P;

(iii) searching matching records independently at each processor using a window of the size w; and

(iv) repeating the processing step for a next cluster of records.

5. The method of claim 4, wherein:

(a) in each group of processors for each database;

(i) N is a number of records in the database;

(ii) P is a number of processors p, and 1≦

p≦

P; and

(iii) C is a number of clusters to be formed per processor p; and

(b) each said comparing step comprises the steps of;

(i) dividing the N records into CP subranges;

(ii) assigning to each processor C clusters of the subranges;

(iii) providing a coordinator processor which reads the database and sends

each record to an appropriate processor where each record is received;

(iv) saving each received record at each processor where it is received in a proper local cluster;

(v) after the coordinator finishes reading and clustering the data among the processors, sorting and applying a window scanning method to the local clusters of each processor.

6. The method according to claim 5, wherein the coordinator processor load balances the various processors using a simple longest processing time first strategy.

18. The method according to claim 1, wherein each said image comprises a document selected from the group consisting of a check, bank deposit or withdrawal slip, coupon, travelers'"'"' cheque, letter of credit, monetary instrument, food stamp, insurance form, medical form, real estate form, an inventory form, real estate document, official government form, brochures, instructional form, questionnaire form, laboratory data form, tax form, computer screen, stock certificate and bond certificate.

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

8. The method of claim 7, further comprising the steps of creating a union of the records that matched the first and second field images, and subjecting the union to transitive closure.

11. The method of claim 7, wherein the field image is a portion of the background.

12. The method of claim 7, wherein the images are checks.

13. The method of claim 7, wherein said residual image comprises handwritten information, further comprising the steps of determining a plurality of spline control points of at least a portion of said residual image.

14. The method according to claim 7, wherein said residual image comprises handwritten information, further comprising the steps of determining a plurality of Fourier coefficients of at least a portion of said residual image.

15. The method according to claim 7, wherein said residual image comprises handwritten information, further comprising the steps of determining a plurality of wavelets of at least a portion of said residual image.

16. The method according to claim 7, wherein said residual image comprises handwritten information, further comprising the steps of determining a plurality of fractal transforms of at least a portion of said residual image.

17. The method according to claim 7, wherein said residual image comprises handwritten information, further comprising the steps of determining a plurality of spatial patterns of at least a portion of said residual image.

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

10. The method of claim 9, further comprising the steps of creating a union of the records that matched the first and second field images, and subjecting the union to transitive closure.