Method for finding and classifying scanned information

• US 5,596,655 A
• Filed: 06/07/1995
• Issued: 01/21/1997
• Est. Priority Date: 08/18/1992
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Lopez, Patricia D.
• Primary Examiner(s): JOHNS, ANDREW W
• Application Number:
  US08/472,359
• Time in Patent Office: 594 Days
• Field of Search: 382/171, 382/173-176, 382/289-290, 382/199, 382/296, 382/282, 382/162, 382/165, 382/291, 382/292, 358/462, 358/464
• US Class Current: 382/173
• CPC Class Codes: G06V 30/413 Classification of content, e.g. text, photographs or tables

Abstract

A system that scans an image into a computer system and then locates left and right edges of information within each row of the image. The system defines top and bottom rows of information as first and last rows of a number of consecutive rows of the image that have a number of pixels between the left and right edges. The system linearizes the edge data, places a left boundary at the leftmost point of the linearized left edge, and places a right boundary at the rightmost point of the linearized right edge. Each pixel within the boundaries is analyzed to classify the pixel as white, light gray, dark gray, black, colored, or as having some color; a percentage of pixels in each class is created; and the image classification is determined using these percentages. The system displays the image and image classification, with the boundary superimposed over the image.

Claims

1. A method for locating graphical information within a scanned image and drawing a bounding rectangle around said information, said method comprising the steps of:

(a) scanning said image into a computer system;

(b) locating left and right edges of information within each row of said image;

(c) locating a top row of said information as a first row of said image having a predetermined number of pixels between left and right edges and defining said top row as a top boundary of said rectangle;

(d) locating a bottom row of said information as a last row of said image having said predetermined number of pixels between left and right edges and defining said bottom row as a bottom boundary of said rectangle;

(e) fitting a first straight line to said left edges and fitting a second straight line to said right edges;

(f) locating a leftmost point of said first straight line and placing a left boundary line of said rectangle at said leftmost point; and

(g) locating a rightmost point of said second straight line and placing a right boundary line of said rectangle at said rightmost point.

2. The method of claim 1 further comprising the steps of:

(h) displaying said image on a graphical output device; and

(i) displaying said bounding rectangle over said image.

3. The method of claim 1 wherein step (b) further comprises the steps of:

(b1) determining an average value of each pixel within each of said rows;

(b2) comparing said average value for each pixel with an average value for a previous pixel; and

(b3) locating said edge at said previous pixel location if said average value for said pixel differs from said average value for said previous pixel by a predetermined edge threshold value.

4. The method of claim 3 wherein step (b1) further comprises the steps of:

(b1a) if said pixel value is a combination of colors, determining said average value by

calculating said average as five times an absolute value of a difference between a red component of said pixel and a red component of a previous pixel plus five times an absolute value of a difference between said red component of said pixel and a red component of a subsequent pixel,

adding to said average eight times an absolute value of a difference between a green component of said pixel and a green component of a previous pixel plus eight times an absolute value of a difference between said green component of said pixel and a green component of a subsequent pixel,

adding to said average three times an absolute value of a difference between a blue component of said pixel and a blue component of a previous pixel plus three times an absolute value of a difference between said blue component of said pixel and a blue component of a subsequent pixel, and

dividing said average by sixteen; and

(b1b) if said pixel value is not a combination of colors, determining said average value by

calculating said average as three times an absolute value of a difference between said pixel and said previous pixel plus three times an absolute value of a difference between said pixel and said subsequent pixel,

adding to said average one and one-half times an absolute value of a difference between said pixel and a next previous pixel plus one and one-half times an absolute value of a difference between said pixel and a next subsequent pixel, and

dividing said average by eight.

5. The method of claim 1 wherein step (e) further comprises the steps of:

(e1) determining a mean and a standard deviation of differences between each pair of edge locations in said left and right edges;

(e2) determining a median of edge locations in said left and right edges;

(e3) determining a difference range from said mean and said standard deviation;

(e4) processing each edge location in said left and right edges comprising the steps of

(e4a) selecting an edge location

(e4b) if a difference between said selected edge location and a previous row edge location exceeds said difference range continuing with step (e4c);

(e4b) if a difference between said selected edge location and a subsequent row edge location does not exceed said difference range, continuing with step (e4a);

(e4c) if a difference between said selected edge location and said median does not exceed said difference range, continuing with step (e4a);

(e4d) if said previous edge location and said subsequent row edge location are both valid edge locations, determining a new value for said edge location as an average of said previous row edge location and said subsequent row edge location and then continuing with step (e4a);

(e4e) if said previous edge location is invalid, determining a new value for said edge location as an average of said subsequent row edge location and said median and then continuing with step (e4a); and

(e4f) if said subsequent edge location is invalid, determining a new value for said edge location as an average of said previous row edge location and said median and then continuing with step (e4a).

6. The method of claim 5 wherein step (e3) comprises determining said difference range as said mean plus one-half said standard deviation.

7. The method of claim 1 further comprising the steps of:

(h) placing each pixel within said boundary into one of a predetermined number of categories determined by the color and shade of said pixel; and

(i) assigning a type to said information, wherein said type is determined by a percentage of pixels in each of said predetermined number of categories.

8. The method of claim 7 wherein step (h) further comprises the steps of:

(h1) establishing said predetermined number of categories as six;

(h2) if said pixel contains color components, placing said pixel comprising the steps of

(h2a) if values of any two of said color components both exceed a predetermined white threshold, placing said pixel into a white category,

(h2b) if values of said color components each fail to exceed a predetermine black threshold, placing said pixel into a black category,

(h2c) defining a weighted average of said color components of said pixel,

(h2d) if differences between values of any two color components and said weighted average exceed a predetermined color threshold, placing said pixel into a colored category,

(h2e) if differences between values of any two color components and said weighted average exceed a predetermined some-color threshold, placing said pixel into a some-colored category,

(h2f) if said weighted average exceeds a predetermined gray threshold, placing said pixel into a light gray category, otherwise placing said pixel into a dark gray category; and

(h3) if said pixel does not contain color components, placing said pixel comprising the steps of

(h3a) if a value of said pixel exceeds said predetermined white threshold, placing said pixel into a white category,

(h3b) if a value of said pixel exceeds a predetermined gray threshold, placing said pixel into a light gray category,

(h3c) if a value of said pixel exceeds said predetermined black threshold, placing said pixel into a dark gray category, and

(h3d) if a value of said pixel does not exceed said predetermined black threshold, placing said pixel into a black category.

9. The method of claim 1 wherein steps (c) and (d) further comprise the steps of:

(c1) locating said top row as a first row of a predetermined number of consecutive rows having said predetermined number of pixels between left and right edges; and

(d1) locating said bottom row as a last row of a predetermined number of consecutive rows having said predetermined number of pixels between left and right edges.

10. A method for determining a type of graphical information within a scanned image, said method comprising the steps of:

(a) scanning said image into a computer system;

(b) placing each pixel within said scanned image into one of a predetermined number of categories determined by the color and shade of said pixel, said placing comprising

(b1) establishing said predetermined number of categories as six;

(b2) if said pixel contains color components, placing said pixel comprising the steps of

(b2a) if values of any two of said color components both exceed a predetermined white threshold, placing said pixel into a white category,

(b2b) if values of said color components each fail to exceed a predetermine black threshold, placing said pixel into a black category,

(b2c) defining a weighted average of said color components of said pixel,

(b2d) if differences between values of any two color components and said weighted average exceed a predetermined color threshold, placing said pixel into a colored category,

(b2e) if differences between values of any two color components and said weighted average exceed a predetermined some-color threshold, placing said pixel into a some-colored category,

(b2f) if said weighted average exceeds a predetermined gray threshold, placing said pixel into a light gray category, otherwise placing said pixel, into a dark gray category, and

(b3) if said pixel does not contain color components, placing said pixel comprising the steps of

(b3a) if a value of said pixel exceeds said predetermined white threshold, placing said pixel into a white category,

(b3b) if a value of said pixel exceeds a predetermined gray threshold, placing said pixel into a light gray category,

(b3c) if a value of said pixel exceeds said predetermined black threshold placing said pixel into a dark gray category, and

(b3d) if a value of said pixel does not exceed said predetermined black threshold, placing said pixel into a black category; and

assigning a type to said information, wherein said type is determined by a percentage of pixels in each of said predetermined number of categories.

11. The method of claim 10 further comprising the steps of:

(d) displaying said image on a graphical output device; and

(e) displaying said type of said image on said graphical output device.

12. A method for locating graphical information within a scanned image and drawing a bounding rectangle around said information, said method comprising the steps of:

(a) scanning said image into a computer system;

(b) locating left and right edges of information within each row of said image;

(c) locating a top row of said information as a first row of said image having a predetermined number of pixels between left and right edges and defining said top row as a top boundary of said rectangle;

(d) locating a bottom row of said information as a last row of said image having said predetermined number of pixels between left and right edges and defining said bottom row as a bottom boundary of said rectangle;

(e) fitting a first straight line to said left edges and fitting a second straight line to said right edges;

(f) locating a leftmost point of said first straight line and placing a left boundary line of said rectangle at said leftmost point;

(g) locating a rightmost point of said second straight line and placing a right boundary line of said rectangle at said rightmost point;

(h) placing each pixel within said rectangle into one of a predetermined number of categories determined by the color and shade of said pixel; and

(i) assigning a type to said information, wherein said type is determined by a percentage of pixels in each of said predetermined number of categories.

13. The method of claim 12 further comprising the steps of:

(j) displaying said image on a graphical output device; and

(k) displaying said bounding rectangle over said image.

14. The method of claim 12 wherein step (b) further comprises the steps of:

(b1) determining an average value of each pixel within each of said rows;

(b2) comparing said average value for each pixel with an average value for a previous pixel; and

(b3) locating said edge at said previous pixel location if said average value for said pixel differs from said average value for said previous pixel by a predetermined edge threshold value.

15. The method of claim 14 wherein step (b1) further comprises the steps of:

(b1a) if said pixel value is a combination of colors, determining said average value by

calculating said average as five times an absolute value of a difference between a red component of said pixel and a red component of a previous pixel plus five times an absolute value of a difference between said red component of said pixel and a red component of a subsequent pixel,

adding to said average eight times an absolute value of a difference between a green component of said pixel and a green component of a previous pixel plus eight times an absolute value of a difference between said green component of said pixel and a green component of a subsequent pixel,

adding to said average three times an absolute value of a difference between a blue component of said pixel and a blue component of a previous pixel plus three times an absolute value of a difference between said blue component of said pixel and a blue component of a subsequent pixel, and

dividing said average by sixteen; and

(b1b) if said pixel value is not a combination of colors, determining said average value by

calculating said average as three times an absolute value of a difference between said pixel and said previous pixel plus three times an absolute value of a difference between said pixel and said subsequent pixel,

adding to said average one and one-half times an absolute value of a difference between said pixel and a next previous pixel plus one and one-half times an absolute value of a difference between said pixel and a next subsequent pixel, and

dividing said average by eight.

16. The method of claim 12 wherein step (e) further comprises the steps of:

(e1) determining a mean and a standard deviation of differences between each pair of edge locations in said left and right edges;

(e2) determining a median of edge locations in said left and right edges;

(e3) determining a difference range from said mean and said standard deviation;

(e4) processing each edge location in said left and right edges comprising the steps of

(e4a) selecting an edge location

(e4b) if a difference between said selected edge location and a previous row edge location exceeds said difference range, continuing with step (e4c);

(e4b) if a difference between said selected edge location and a subsequent row edge location does not exceed said difference range, continuing with step (e4a);

(e4c) if a difference between said selected edge location and said median does not exceed said difference range, continuing with step (e4a);

(e4d) if said previous edge location and said subsequent row edge location are both valid edge locations, determining a new value for said edge location as an average of said previous row edge location and said subsequent row edge location and then continuing with step (e4a);

(e4e) if said previous edge location is invalid, determining a new value for said edge location as an average of said subsequent row edge location and said median and then continuing with step (e4a); and

(e4f) if said subsequent edge location is invalid, determining a new value for said edge location as an average of said previous row edge location and said median and then continuing with step (e4a).

17. The method of claim 16 wherein step (e3) comprises determining said difference range as said mean plus one-half said standard deviation.

18. The method of claim 12 wherein step (h) further comprises the steps of:

(h1) establishing said predetermined number of categories as six;

(h2) if said pixel contains color components, placing said pixel comprising the steps of

(h2a) if values of any two of said color components both exceed a predetermined white threshold, placing said pixel into a white category,

(h2b) if values of said color components each fail to exceed a predetermine black threshold, placing said pixel into a black category,

(h2c) defining a weighted average of said color components of said pixel,

(h2d) if differences between values of any two color components and said weighted average exceed a predetermined color threshold, placing said pixel into a colored category,

(h2e) if differences between values of any two color components and said weighted average exceed a predetermined some-color threshold, placing said pixel into a some-colored category,

(h2f) if said weighted average exceeds a predetermined gray threshold, placing said pixel into a light gray category, otherwise placing said pixel into a dark gray category; and

(h3) if said pixel does not contain color components, placing said pixel comprising the steps of

(h3a) if a value of said pixel exceeds said predetermined white threshold, placing said pixel into a white category,

(h3b) if a value of said pixel exceeds a predetermined gray threshold, placing said pixel into a light gray category,

(h3c) if a value of said pixel exceeds said predetermined black threshold, placing said pixel into a dark gray category, and

(h3d) if a value of said pixel does not exceed said predetermined black threshold, placing said pixel into a black category.

19. The method of claim 12 wherein steps (c) and (d) further comprise the steps of:

(c1) locating said top row as a first row of a predetermined number of consecutive rows having said predetermined number of pixels between left and right edges; and

(d1) locating said bottom row as a last row of a predetermined number of consecutive rows having said predetermined number of pixels between left and right edges.