Method and apparatus for automatic cleaning and enhancing of scanned documents

• US 7,016,536 B1
• Filed: 11/21/2000
• Issued: 03/21/2006
• Est. Priority Date: 11/24/1999
• Status: Expired due to Term

• Current Assignee: GTX Europe, Ltd.
• Original Assignee: GTX Corp.
• Inventors: Ling, Marvin T., Higgins, Michael E., Foster, Philip B., Filipski, Alan J.
• Primary Examiner(s): Lee, Thomas D.
• Assistant Examiner(s): BRINICH, STEPHEN M
• Application Number:
  US09/717,607
• Time in Patent Office: 1,946 Days
• Field of Search: 382190-194, 382181-184, 382/232, 382/243, 382/254, 382289-290
• US Class Current: 382/190
• CPC Class Codes: G06T 2207/10008 from scanner, fax or copier
• CPC Class Codes: G06T 2207/30176 Document
• CPC Class Codes: G06T 5/70 Denoising; Smoothing
• CPC Class Codes: G06T 5/80 Geometric correction
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/15 Cutting or merging image elements, e.g. region growing, watershed or clustering-based techniques

Abstract

A method and apparatus are provided for removing noise from a first digital representation of data images and noise images of a document, including digitally scanning the document so as to produce the first digital representation of all the images of the document, including the data images and the noise images. After de-skewing the image representation, objects are built from a reduced-resolution representation of the scanned representation. Objects identified as picture objects are included in a mask which is logically ANDed with the de-skewed representation of the scanned document. All objects are added to an object list and initially marked as noise. Objects identified as text objects or geometric objects are marked as data objects. Objects identified as picture objects are included in a mask which is logically ANDed with the de-skewed representation to eliminate all other objects. Objects marked as data objects are added to that representation to provide the de-skewed, de-speckled representation of the scanned document.

Claims

1. A method for producing a cleaned-up digital image of a document including essential data images and undesired noise images, comprising:

(a) digitally scanning the document to produce a first digital representation of the data images and the noise images;

(b) performing a first object grabbing operation on the first digital representation to identify all object images thereof;

(c) determining a skew angle of a straight line having a predetermined relationship to some objects representative of the essential data images and de-skewing the document by rotating the first digital representation by an amount equal to the magnitude of the skew angle to provide a de-skewed first digital representation;

(d) performing a second object grabbing operation on the de-skewed first digital representation to create an object list of all object images of the de-skewed first digital representation;

(e) identifying a portion of the de-skewed first digital representation corresponding to a picture region of the document;

(f) producing a reduced-resolution representation of the de-skewed first digital representation and performing a second object grabbing operation on the reduced-resolution representation;

(g) identifying objects of the reduced-resolution representation representing essential data areas of the document; and

(h) constructing the cleaned-up digital image of the document by performing a logical ANDing operation between the picture region and the data areas with the de-skewed first digital representation to eliminate all objects outside of the picture region and the data areas to provide the cleaned-up digital image.

2. A method for producing a cleaned-up digital image of a document including essential data images and undesired noise images, comprising:

(a) digitally scanning the document to produce a first digital representation of the data images and the noise images;

(b) performing a first object grabbing operation on the first digital representation to identify all object images thereof;

(c) determining a skew angle of a straight line having a predetermined relationship to some objects representative of the essential data images and de-skewing the document by rotating the first digital representation by an amount equal to the magnitude of the skew angle to provide a de-skewed first digital representation;

(d) performing a second object grabbing operation on the de-skewed first digital representation to create an object list of all object images of the de-skewed first digital representation;

(e) identifying a portion of the de-skewed first digital representation corresponding to a picture region of the document;

(f) identifying objects representing essential data images of the document and marking the identified objects as data objects; and

(g) constructing the cleaned-up digital image of the document by

i. combining the objects in the picture region and the marked data objects, and

ii. eliminating all objects not marked as data objects to provide a reconstructed digital representation of the essential images without the noise images.

3. The method of claim 2 including performing the first object grabbing operation by obtaining serial runlength data from the first digital representation including slices that each include the length and ending pixel number of a string of connected pixels having a “

1”

value, operating line-by-line on the runlength data by means of a decision tree classifier that creates software objects including a first linked list of a number of further linked lists each of which contains all of the slices of an object image, entering the slices of the object image into a software frame in the same order in which the slices are scanned, determining if the object image can be represented as a trapezoid or as an irregular blob containing all of its slices, fitting the data in the software frame representing the object image into a decision tree classifier, and operating the classifier to recognize and assign identifiers to divergences, convergences, and open ends of the object image and create a new linked list of linked lists representing the object image in the form of blob records, trapezoid records, divergence records, and convergence records which then can be conveniently used in subsequent vectorization operations without the need to scan and recognize data representing the object image.

4. The method of claim 3 including performing the second object grabbing operation by performing steps which are essentially similar to the steps of the first object grabbing operation.

5. The method of claim 2 wherein in step (c) the line has the predetermined relationship to a plurality of text objects in a row of text objects.

6. The method of claim 5 wherein some of the text objects are centered about the line.

7. The method of claim 5 including building the row of text objects by successively adding any closest nearby text object to either end of a row initially including a first text object.

8. The method of claim 3 wherein in step (c) the line has the predetermined relationship to a plurality of geometric objects identified by vectorizing objects larger than a predetermined size, identifying near-horizontal lines and near-vertical lines of the vectorized objects, and selecting a value of the skew angle which minimizes the mean-square deviation of the near-horizontal and near-vertical lines from orthogonality.

9. The method of claim 2 including, after step (b), classifying at least a portion of the document as a type including mainly text objects or mainly geometric objects by producing a first reduced-resolution representation of the first digital representation and performing another object grabbing operation on the first reduced-resolution representation to identify objects of the first reduced-resolution representation, determining the numbers of text-character-shaped rectangular objects and geometric objects thereof, respectively, and classifying the document as text type if the number of text-character-shaped objects is greater than the number of geometric objects, and otherwise classifying the document as geometric type.

10. The method of claim 2 wherein step (f) includes forming a row of text including text objects near to each other and having heights within a predetermined range, and marking all object images produced according to step (b) within the row as data objects.

11. The method of claim 10 including identifying the object images which are geometric objects and marking them as data objects.

12. The method of claim 11 wherein the identifying of geometric objects includes identifying only objects which have sufficiently high density and a sufficiently large aspect ratio as geometric objects.

13. The method of claim 11 wherein the identifying of geometric objects includes identifying whole geometric objects by getting a next object image having a size greater than a predetermined text size, and, if the next object image has a density lower than a predetermined density, performing a neural network operation to determine if the next object image is a whole geometry object, and, if the neural network operation determines that the next object image is a whole geometry object, marking the next object image as a data object.

14. The method of claim 11 wherein the identifying of geometric objects includes identifying broken geometry objects by performing a quad tree operation on all object images not previously identified as either text objects or geometric objects to identify a non-marked object, and repeatedly identifying any nearby non-marked objects of similar shape, to attempt to extend a pattern of similar non-marked objects in opposite directions from the non-marked object, and marking all objects included in the pattern as data objects.

15. The method of claim 14 including computing a pattern confidence level, and marking the objects included in the pattern only if the confidence level exceeds a predetermined level.

16. The method of claim 11 including identifying any object images which constitute dashed lines or dotted lines and marking such identified object images as data objects, by creating a grid of the wide, short rectangles or a grid of tall, narrow rectangles covering at least a portion of the document, summing the areas of all dash-sized for dot-sized objects into appropriate rectangles, eliminating objects in the appropriate rectangles having sufficiently small area sums, obtaining a histogram all objects in the appropriate rectangles by area and x-coordinate or y-coordinate, and marking each object having a sufficiently large histogram peak and located between predetermined coordinate bounds has a dashed object.

17. The method of claim 2 wherein the producing of the reduced-resolution representation of the de-skewed first digital representation includes representing each tile of four adjacent pixels of the first digital representation as a single pixel and setting the single pixel to a “

1”

state if any of the four adjacent pixels of the tile is at a “

1”

state and otherwise setting the single pixel to a “

0”

state.

18. The method of claim 17 including producing a first reduced-resolution representation of the first digital representation by representing each tile of four adjacent pixels of the reduced-resolution representation as a single pixel and setting that single pixel to a “

1”

state if any of the four adjacent pixels of that tile is at a “

1”

state and otherwise setting that single pixel to a “

0”

state.

19. A method for producing a cleaned-up digital image of a document including essential data images and undesired noise images, comprising:

(a) digitally scanning the document to produce a first digital representation of the data images and the noise images;

(b) operating a processor to perform a first object grabbing operation on the first digital representation to identify all object images thereof;

(c) operating the processor to determine a skew angle of a straight line having a predetermined relationship to at least some objects representative of essential data and to de-skew the document by rotating the first digital representation by an amount equal to the magnitude of the skew angle to provide a de-skewed first digital representation;

(d) operating the processor to perform a second object grabbing operation on the de-skewed first digital representation to create an object list of all object images of the de-skewed first digital representation;

(e) operating the processor so as to identifying a portion of the de-skewed first digital representation corresponding to a picture region of the document;

(f) operating the processor to produce a reduced-resolution representation of the de-skewed first digital representation and to perform a second object-grabbing operation on the reduced resolution representation;

(g) operating the processor to identify objects of the reduced-resolution representation representing essential data areas of the document; and

(h) constructing the cleaned-up digital image of the document by operating the processor to perform a logical ANDing operation between the picture region and the data areas with the de-skewed first digital representation to eliminate all objects outside of the picture region and the data areas to provide the cleaned-up digital image.

20. A method for producing a cleaned-up digital image of a document including essential data images and undesired noise images, comprising:

(a) digitally scanning the document to produce a first digital representation of the data images and the noise images;

(b) operating a processing system to perform a first object grabbing operation on the first digital representation to identify all object images thereof;

(c) operating the processing system to determine a skew angle of a straight line having a predetermined relationship to at least some objects representative of essential data and to de-skew the document by rotating the first digital representation by an amount equal to the magnitude of the skew angle to provide a de-skewed first digital representation;

(d) operating the processing system to perform a second object grabbing operation on the de-skewed first digital representation to create an object list of all object images of the de-skewed first digital representation;

(e) operating the processing system so as to identify a portion of the de-skewed first digital representation corresponding to a picture region of the document;

(f) operating the processing system to identify objects representing essential data images of the document and mark the identified objects as data objects; and

(g) constructing the cleaned-up digital image of the document by operating the processing system to

i. combine the objects in the picture region and the marked data objects to provide the cleaned-up digital image, and

ii. eliminate all objects not marked as data objects to provide a reconstructed digital representation of the essential images without the noise images.