Method and apparatus for separating document image object types

• US 6,411,733 B1
• Filed: 11/25/1998
• Issued: 06/25/2002
• Est. Priority Date: 11/25/1998
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Saund, Eric
• Primary Examiner(s): Mehta, Bhavesh
• Assistant Examiner(s): Bayat, Ali
• Application Number:
  US09/199,699
• Time in Patent Office: 1,308 Days
• Field of Search: 382/181, 382/182, 382/183, 382/184, 382/185, 382/186, 382/187, 382/188, 382/189, 382/190, 382/191, 382/192, 382/200, 382/201, 382/258, 382/257, 382/256, 382/254
• US Class Current: 382/190
• CPC Class Codes: G06V 30/413 Classification of content, e.g. text, photographs or tables

Abstract

A method and apparatus is provided for segmenting a binary document image so as to assign image objects to one of three types: CHARACTER-type objects, STROKE-type objects, and LARGE-BITMAP-type objects. The method makes use of a contour tracing technique, statistical analysis of contour features, a thinning technique, and image morphology.

Claims

1. A method for separating types of objects present in an image, the method comprising steps of:

a) inputting the image having objects including character type objects stroke type objects and blob type objects;

b) generating a first bitmap representing the image;

c) determining which of the objects of the image are of the character type by comparing predetermined decision criteria to data obtained from the first bitmap by;

i) performing boundary contour tracing on the objects represented in the first bitmap to obtain a contour of each of the objects,

ii) measuring a width and height of each contour based on a boundary box thereof,

iii) measuring a perimeter of the each contour,

iv) measuring an area of the each contour,

v) determining a ratio of the perimeter to the area for the each contour, and

vi) measuring a wiggliness of the each contour;

d) separating character type objects from the first bitmap to obtain a second bitmap, having only characters represented therein, and a third bitmap;

e) performing N−

1 thinning steps on the third bitmap to obtain a fourth bitmap;

f) copying the fourth bitnmap to obtain a fifth bitmap;

g) performing another thinning step on the fourth bitmap;

h) removing all non-interior pixels of the fifth bitmap to obtain a sixth bitmap;

i) performing an image morphology based dilation on the sixth bitmap to restore pixels eroded by the thinning and removing steps and obtain a seventh bitmap;

j) performing a bitwise boolean operation between the first bitmap and the seventh bitmap to obtain an eighth bitmap having only blob type objects represented therein;

k) performing a bitwise boolean operation between the fourth bitmap and the eighth bitmap to obtain a ninth bitmap; and

,

l) performing a tracing operation on the ninth bitmap to obtain a tenth bitmap having only stroke type objects represented therein.

2. The method as set forth in claim 1 wherein the boolean operation of step j) is an AND operation.

3. The method as set forth in claim 1 wherein the boolean operation of step k) is an AND NOT operation.

4. The method as set forth in claim 1 further comprising obtaining a representation of the character type objects based on the second bitmap.

5. The method as set forth in claim 1 wherein the obtaining of the second bitmap comprises copying the separated character objects to a separate bitmap and performing boolean operations between the first bitmap and the separate bitmap.

6. The method as set forth in claim 1 further comprising obtaining a representation of the blob type objects based on the eighth bitmap.

7. The method as set forth in claim 1 further comprising obtaining a representation of the stroke type objects based on the tenth bitmap.

8. The method as set forth in claim 1 wherein the wiggliness of each contour is determined based on a sum-squared curvature of the contour.

9. A method for separating types of objects present in an image, the method comprising steps of:

a) inputting the image having objects including character type objects, stroke type objects and blob type objects;

b) generating a first bitmap representing the image;

c) determining which of the objects of the image are of the character type by comparing predetermined decision criteria to data obtained from the first bitmap;

d) separating character type objects from the first bitmap to obtain a second bitmap, having only characters represented therein, and a third bitmap;

e) performing N−

1 thinning steps on the third bitmap to obtain a fourth bitmap;

f) copying the fourth bitmap to obtain a fifth bitmap;

g) performing another thinning step on the fourth bitmap;

h) removing all non-interior pixels of the fifth bitmap to obtain a sixth bitmap;

i) performing an image morphology based dilation on the sixth bitmap to restore pixels eroded by the thinning and removing steps and obtain a seventh bitmap;

j) performing a bitwise boolean operation between the first bitmap and the seventh bitmap to obtain an eighth bitmap having only blob type objects represented therein;

k) performing a bitwise boolean operation between the fourth bitmap and the eighth bitmap to obtain a ninth bitmap; and

,

l) performing a tracing operation on the ninth bitmap to obtain a tenth bitmap having only stroke type objects represented therein.

10. The method as set forth in claim 9 wherein the boolean operation of step j) is an AND operation.

11. The method as set forth in claim 9 wherein the boolean operation of step k) is an AND NOT operation.

12. The method as set forth in claim 9 further comprising obtaining a representation of the character type objects based on the second bitmap.

13. The method as set forth in claim 9 wherein the obtaining of the second bitmap comprises copying the separated character objects to a separate bitmap and performing boolean operations between the first bitmap and the separate bitmap.

14. The method as set forth in claim 9 further comprising obtaining a representation of the blob type objects based on the eighth bitmap.

15. The method as set forth in claim 9 further comprising obtaining a representation of the stroke type objects based on the tenth bitmap.

16. The method as set forth in claim 9 wherein step c) comprises

i) performing boundary contour tracing on the objects represented in the first bitmap to obtain a contour of each of the objects,

ii) measuring a width and height of each contour based on a boundary box thereof,

iii) measuring a perimeter of the each contour,

iv) measuring an area of the each contour,

v) determining a ratio of the perimeter to the area for the each contour, and

vi) measuring a wiggliness of the each contour.

17. The method as set forth in claim 16 wherein the wiggliness of each contour is determined based on a sum-squared curvature of the contour.

18. A method for separating types of objects present in an image, the method comprising steps of:

a) inputting the image having objects including character type objects, stroke type objects and blob type objects;

b) generating a first bitmap representing the image;

c) determining which of the objects of the image are of the character type by comparing predetermined decision criteria to data obtained from the first bitmap;

d) separating character type objects from the first bitmap to obtain a second bitmap, having only characters represented therein, and a third bitmap; and

,

e) separating stroke type objects and blob type objects of the image, respectively, by selectively using techniques of thinning, dilation, and bitwise logical operations on at least one of the first and third bitmaps.

19. The method as set forth in claim 18 wherein step c) comprises:

f) performing N−

1 thinning steps on the third bitmap to obtain a fourth bitmap;

g) copying the fourth bitmap to obtain a fifth bitmap;

h) performing another thinning step on the fourth bitmap;

i) removing all non-interior pixels of the fifth bitmap to obtain a sixth bitmap;

j) performing an image morphology based dilation on the sixth bitmap to restore pixels eroded by the thinning and removing steps and obtain a seventh bitmap;

k) performing a bitwise boolean operation between the first bitmap and the seventh bitmap to obtain an eighth bitmap having only blob type objects represented therein;

l) performing a bitwise boolean operation between the fourth bitmap and the eighth bitmap to obtain a ninth bitmap; and

,

m) performing a tracing operation on the ninth bitmap to obtain a tenth bitmap having only stroke type objects represented therein.

20. A system for separating types of objects present in an input image having character type objects, stroke type objects and blob type objects, the system comprising:

means for generating a first bitmap representing the image;

means for determining which of the objects of the image are of the character type by comparing predetermined decision criteria to data obtained from the first bitmap;

means for separating character type objects from the first bitmap to obtain a second bitmap, having only characters represented therein, and a third bitmap; and

,

means for separating stroke type objects and blob type objects of the image, respectively, by selectively using techniques of thinning, dilation, and bitwise logical operations on at least one of the first and third bitmaps.

21. The system as set forth in claim 20 wherein the means for separating stroke type objects and blob type objects comprises means for 1) performing N−

1 thinning steps on the third bitmap to obtain a fourth bitmap,

     2) copying the fourth bitmap to obtain a fifth bitmap,

     3) performing another thinning step on the fourth bitmap,

     4) removing all non-interior pixels of the fifth bitmap to obtain a sixth bitmap,

     5) performing an image morphology based dilation on the sixth bitmap to restore pixels eroded by the thinning and removing steps and obtain a seventh bitmap,

     6) performing a bitwise boolean operation between the first bitmap and the seventh bitmap to obtain an eighth bitmap having only blob type objects represented therein,

     7) performing a bitwise boolean operation between the fourth bitmap and the eighth bitmap to obtain a ninth bitmap and

     8) performing a tracing operation on the ninth bitmap to obtain a tenth bitmap having only stroke type objects represented therein.

22. The system as set forth in claim 20 wherein the means for determining comprises means for 1) performing boundary contour tracing on the objects represented in the first bitmap to obtain a contour tracing on the objects represented in the first bitmap to obtain a contour of each of the objects, 2) measuring a width and height of each contour based on a boundary box thereof, 3) measuring a perimeter of the each contour, 4) measuring an area of the each contour, 5) determining a ratio of the perimeter to the area for the each contour and 6) measuring a wiggliness of the each contour.