Electronic retrieval of information from form documents

• US 5,694,494 A
• Filed: 09/13/1996
• Issued: 12/02/1997
• Est. Priority Date: 04/12/1993
• Status: Expired due to Term

• Current Assignee: Ricoh Company Limited, Ricoh Corporation (Ricoh Company Limited)
• Original Assignee: Ricoh Company Limited, Ricoh Corporation (Ricoh Company Limited)
• Inventors: Mizutani, Mitsutoshi, Peairs, Mark, Hart, Peter
• Primary Examiner(s): COUSO, YON JUNG
• Application Number:
  US08/712,663
• Time in Patent Office: 445 Days
• Field of Search: 382/163, 382/175, 382/176, 382/305, 382/306, 382/257, 382/254, 358/464, 358/462, 358/447, 358/453, 358/455
• US Class Current: 382/305
• CPC Class Codes: G06T 5/20 using local operators
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/155 Removing patterns interfering with the pattern to be recognised, such as ruled lines or underlines

Abstract

A method for retrieving user-supplied information from a scanned version of a completed document is described. The method includes the steps of obtaining a first image of the document having information printed thereon in its blank format before other information has been added to it by the user. A second image of the document is obtained after information has been added to it by the user. The two images are aligned, and for each pixel in the first image which corresponds to information on the document, those pixels are deleted from the second image to create an image which corresponds to subtraction of the first image from the second image. Finally, a step is performed to electronically restore the information added by the user which was deleted during the subtraction operation.

Claims

1. A method of electronically distinguishing information added to a form document from the form document itself, and of retrieving the information from said form document, the method comprising the steps of:

obtaining a first digital image of a form document to produce a first array of pixels representing printed areas of said form document, wherein each pixel of said first array of pixels has a pixel location and a pixel value;

obtaining a second digital image of said form document having information added thereto to produce a second array of pixels representing printed areas of said form document and added information, wherein each pixel in said second array of pixels has a pixel location and a pixel value;

identifying a subset of pixels in said second array which correspond to said first array of pixels by aligning the pixel locations of said first array of pixels with said second array of pixels;

deleting the pixel value of each pixel in said subset of pixels, irrespective of whether any of said subset of pixels also correspond to said added information;

designating as "unknown" the pixel value of those pixels whose pixel values were deleted in said deleting step, thereby producing a set of dropout pixels; and

estimating a pixel value for one or more pixels in said set of dropout pixels to produce a third digital image representing said added information apart from said form document itself.

2. A method as in claim 1 wherein the step of estimating a pixel value for one or more pixels in said set of dropout pixels comprises the steps of:

(a) specifying a neighborhood configuration and a threshold value;

(b) selecting a dropout pixel from said set of dropout pixels;

(c) counting a number of neighborhood pixels having a known pixel value, said neighborhood pixels being in a neighborhood region relative to said dropout pixel as defined by said neighborhood configuration;

(d) calculating a pixel value for said dropout pixel when said number of neighborhood pixels having a known pixel value exceeds said threshold value;

(e) selecting another dropout pixel from said set of dropout pixels;

(f) repeating steps (c) through (e) until there are no pixels remaining in said set of dropout pixels having a number of neighborhood pixels of known value which exceeds said threshold value; and

(g) adjusting said threshold value, when desired, and repeating steps (c) through (f) until a number of pixels in said set of dropout pixels having a pixel value of "unknown" is less than a desired quantity.

3. A method as in claim 2 wherein the neighborhood configuration comprises a geometrical region immediately adjacent to and encompassing said dropout pixel.

4. A method as in claim 2 wherein the threshold value is a number smaller than the number of pixels encompassed by said neighborhood region.

5. A method as in claim 2 wherein the step of calculating a pixel value for said dropout pixel comprises a step of performing a mathematical operation on the pixel values of those pixels in the neighborhood region having a known pixel value.

6. A method as in claim 2 wherein the pixels are arranged in a matrix and the neighborhood configuration comprises a 3×

3 pixel matrix surrounding said dropout pixel.

7. A method as in claim 2 wherein step (g) further includes the step of decrementing the threshold value by one.

8. A method as in claim 1 further comprising a step of applying a dilation filter to the first array of pixels to produce an expanded first array of pixels having an increased number of pixels for representing printed areas of said form document.

9. A method as in claim 1 wherein the step of obtaining a second digital image further comprises electronically scanning the form document having information added thereto to obtain a second stored image thereof.

10. A method as in claim 9 wherein the step of obtaining a first digital image further comprises scanning the form document to obtain a first stored image thereof.

11. A method as in claim 10 further comprising a step of dilating said first array of pixels before said step of aligning.

12. A method for restoring pixels in an image represented by pixels having known pixel values and pixels to be restored having unknown pixel values, the method comprising the steps of:

(a) obtaining, external to the image, an indication of which pixels have unknown pixel values;

(b) specifying a threshold value and a neighborhood configuration, the neighborhood configuration defining a windows;

(c) restoring each pixel having an unknown pixel value, by the steps of;

(1) positioning the window relative to the pixel to be restored;

(2) counting a number of pixels having known values in the window to obtain a known pixel count;

(3) calculating, when the known pixel count exceeds the threshold value, a restored pixel value, said restored pixel value being a function of the pixel values of the pixels in the window having known pixel values;

(4) assigning, when the known pixel count exceeds the threshold value, the restored pixel value to the pixel to be restored; and

(5) repeating steps (1)-(4) until there are no pixels having unknown values remaining whose known pixel count exceeds the threshold value; and

(d) adjusting the threshold value, when desired, and repeating step (c) above until a number of pixels having unknown values is less than a desired quantity.

13. A method as in claim 12 wherein the step of calculating a restored pixel value comprises a step of calculating an average of the pixel values of the pixels in the window having known pixel values.

14. A method as in claim 12 wherein the step of calculating a restored pixel value comprises a step of calculating a weighted average of the pixel values of the pixels in the window having known pixel values.

15. A method as in claim 12 wherein the step of calculating a restored pixel value comprises a step of calculating a rounded value of a weighted average of the pixel values of the pixels in the window having known pixel values.

16. A method as in claim 12 wherein the neighborhood configuration comprises a geometrical region immediately adjacent to and encompassing the pixel to be restored.

17. A method as in claim 12 wherein the threshold value is a number smaller than the number of pixels in the window.

18. A method as in claim 12 wherein the pixels are arranged in a matrix and the neighborhood configuration comprises a 3×

3 pixel matrix surrounding said pixel to be restored.

19. A method as in claim 18 wherein the threshold value is 7.

20. A method as in claim 12 wherein step (d) further includes the step of decrementing the threshold value by one.

21. A method as in claim 12 wherein the step of specifying a threshold value includes a step of specifying a threshold value dependent on the pixel values of pixels in the window.

22. A method as in claim 12 wherein the desired quantity is zero.

23. A computing system for restoring pixels in an image represented by pixels having known pixel values and pixels to be restored having unknown pixel values, the system comprising:

(a) means for obtaining, external to the image, an indication of which pixels have unknown pixel values;

(b) means for specifying a threshold value, a neighborhood configuration and a desired quantity of unrestored pixels, wherein the neighborhood configuration defines a window;

(c) means, coupled to said means for obtaining and said means for specifying, for restoring each pixel having an unknown pixel value, including;

(1) means for positioning the window relative to the pixel to be restored;

(2) means for counting a number of pixels having known values in the window to obtain a known pixel count;

(3) means for comparing the known pixel count to said threshold value;

(4) means, coupled to the means for comparing the known pixel count, for calculating a restored pixel value when the known pixel value exceeds said threshold value, wherein the restored pixel value is calculated as a function of the pixel values of the pixels in the window having known pixel values;

(4) means, coupled to the means for comparing, assigning the restored pixel value to the pixel to be restored when the known pixel count exceeds the threshold value; and

(5) means for determining when no pixels having unknown values whose known pixel count exceeds the threshold value remain;

(6) means, coupled to said means for determining, for repeating the operation of the means for positioning, the means for counting, the means for comparing, the means for calculating, the means for assigning, and the means for determining, until no pixels having unknown values whose known pixel count exceeds the threshold value remain;

(d) means for comparing a number of unrestored pixels having an unknown value to the desired quantity of unrestored pixels; and

(e) means, coupled to the means for comparing a number of unrestored pixels and the means for restoring, for selectively adjusting the threshold value, and for repeating the operation of the means for restoring until the number of pixels having unknown values is less than the desired quantity of unrestored pixels.

24. A computing system as in claim 23 wherein the means for obtaining an indication is a means for reading a digitized image of a blank form, the pixels in the digitized image of an obscuring value being the indicated pixels.

25. A computing system as in claim 23 wherein the means for obtaining an indication includes dilation means for dilating the blank form, thereby increasing the number of pixels indicated.