Method and system for document segmentation

• US 6,904,170 B2
• Filed: 05/17/2002
• Issued: 06/07/2005
• Est. Priority Date: 05/17/2002
• Status: Active Grant

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Chao, Hui, Bloomberg, Dan
• Primary Examiner(s): Tran, Phuoc
• Application Number:
  US10/150,362
• Publication Number:
  US 20030215136A1
• Time in Patent Office: 1,117 Days
• Field of Search: 382/174, 382/176, 382/179, 382/199, 382/281, 382/290
• US Class Current: 382/174
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/1478 of characters or characters lines

Abstract

A method of document segmentation. Specifically, one embodiment of the present invention discloses a method of document segmentation that performs a plurality of projection profiles of pixel intensities on a document containing a plurality of text lines over a range of angles. A plurality of slope values for a plurality of discrete distances perpendicular to said range of angles is calculated for the plurality of projection profiles. A set of maximum absolute slope values is sorted out from the plurality of slope values. Text lines of first and second type are identified by setting a threshold slope value. Absolute slope values greater than the threshold slope value indicate the plurality of text lines of said first type. Absolute slope values less than the threshold slope value indicate the plurality of text lines of a second type.

Claims

1. A method of document segmentation comprising:

a) generating a plurality of projection profiles of pixel intensities for a document containing a plurality of text lines including a plurality of text lines of a first type and a plurality of text lines of a second type over a range of angles;

b) calculating a plurality of slope values of said plurality of projection profiles for a plurality of discrete distances perpendicular to said range of angles;

c) sorting out a set of maximum absolute slope values of said plurality of slope values; and

d) identifying text lines of said first and second type by setting a threshold slope value wherein absolute slope values greater than said threshold slope value indicate said plurality of text lines of said first type, and absolute slope values less than said threshold slope value indicate said plurality of text lines of said second type.

2. The method of document segmentation as described in claim 1, wherein a) further comprises:

calculating a plurality of Hough transforms for said plurality of projection profiles in two dimensions including said range of angles and said plurality of discrete distances.

3. The method of document segmentation as described in claim 2, wherein b) further comprises:

calculating a plurality of first derivatives of said plurality of Hough transforms for said plurality of discrete distances over said range of angles.

4. The method of document segmentation as described in claim 3, wherein c) further comprises:

for each of said plurality of discrete distances, sorting out a maximum absolute slope value first derivative over said range of angles, said maximum absolute slope value first derivative corresponding to a local skew angle of an associated text line.

5. The method of document segmentation as described in claim 4, further comprising:

calculating a global skew angle of said plurality of text lines of said first type; and

verifying slope angles corresponding to said set of maximum absolute slope values that are greater than said threshold value are associated with said plurality of text lines of a first type by comparing said slope angles to said global skew angle.

6. The method of document segmentation as described in claim 1, wherein d) further comprises:

arranging said set of maximum absolute slope values of said plurality of slope values from minimum slope values to maximum slope values;

locating a first Gaussian distribution of associated with said plurality of text lines of a first type;

locating a second Gaussian distribution of said plurality of text lines of a second type; and

setting said threshold slope value between said first and second Gaussian distributions.

7. The method of document segmentation as described in claim 1, wherein d) further comprises:

pairing said plurality of slope values to indicate x-height lines and baselines of said plurality of text lines.

8. The method of document segmentation as described in claim 1, further comprising:

scanning said document to obtain a digital image of said document comprising a plurality of pixels, said scanning performed before said performing said plurality of projection profiles.

9. The method of document segmentation as described in claim 1, wherein said plurality of text lines of a first type comprise a plurality of text lines of machine printed text, and said plurality of text lines of a second type comprise a plurality of text lines of handwritten annotations.

10. The method of document segmentation as described in claim 1, wherein text lines of said first type are more uniform than text lines of said second type.

11. A method of document segmentation comprising:

a) generating a plurality of projection profiles of pixel intensities for a digitized document containing a plurality of text lines including a plurality of handwritten text lines and a plurality of machine printed text lines over a range of angles;

b) calculating a plurality of slope values of said plurality of projection profiles for a plurality of discrete distances perpendicular to said range of angles;

c) sorting out a set of maximum absolute slope values of said plurality of slope values, said set of maximum absolute slope values associated with a plurality of local skew angles for said plurality of handwritten text lines and said plurality of machine printed text lines; and

d) identifying said plurality of machine printed text lines and said plurality of handwritten text lines by setting a threshold absolute slope value, wherein a first maximum absolute slope value greater than said threshold slope value indicates one of said plurality of machine printed text lines and a second maximum absolute slope value less than said threshold absolute slope value indicates one of said plurality of handwritten text lines.

12. The method of document segmentation as described in claim 11, wherein a) further comprises:

calculating a plurality of Hough transforms for said plurality of projection profiles as a function of said range of angles and said plurality of discrete distances.

13. The method of document segmentation as described in claim 12, wherein b) further comprises:

calculating a plurality of first derivatives of said plurality of Hough transforms for said plurality of discrete distances over said range of angles.

14. The method of document segmentation as described in claim 12, wherein d) further comprises:

d1) determining a first and second sharpness of slope transitions over a first delta distance and a second delta distance for each of said set of maximum absolute slope values, wherein said second delta distance is greater than said first delta distance;

d2) identifying text lines of said plurality of machine printed text lines when said first and second sharpness of slope transitions are relatively equal; and

d3) identifying text lines of said plurality of handwritten text lines when said first and second sharpness of slope transitions are different.

15. The method of document segmentation as described in claim 14, wherein d1) further comprises:

calculating second derivatives of an associated Hough transform over said first delta distance and said second delta distance.

16. The method of document segmentation as described in claim 11, wherein d) further comprises:

pairing said plurality of slope values to indicate x-height lines and baselines of said plurality of text lines.

17. The method of document segmentation as described in claim 16, wherein said x-height lines of said plurality of text lines are associated with maximum absolute slope values that were originally positive.

18. The method of document segmentation as described in claim 16, wherein said baselines of said plurality of text lines are associated with maximum absolute slope values that were originally negative.

19. The method of document segmentation as described in claim 11, wherein d) further comprises:

identifying a second plurality of text lines of a type different than said machine printed text lines and said handwritten text lines by setting a second threshold absolute slope value, wherein a third maximum absolute slope value less than said second threshold slope value indicates one of said second plurality of text lines.

20. A computer system comprising:

a processor; and

a computer readable memory coupled to said processor and containing program instructions that, when executed, implement a method of document segmentation comprising;

a) generating a plurality of projection profiles of pixel intensities for a document containing a plurality of text lines including a plurality of text lines of a first type and a plurality of text lines of a second type over a range of angles;

b) calculating a plurality of slope values of said plurality of projection profiles for a plurality of discrete distances perpendicular to said range of angles;

c) sorting out a set of maximum absolute slope values of said plurality of slope values; and

d) identifying text lines of said first and second type by setting a threshold slope value wherein absolute slope values greater than said threshold slope value indicate said plurality of text lines of said first type, and absolute slope values less than said threshold slope value indicate said plurality of text lines of said second type.

21. The computer system as described in claim 20, wherein a) in said method further comprises:

calculating a plurality of Hough transforms for said plurality of projection profiles in two dimensions including said range of angles and said plurality of discrete distances.

22. The computer system as described in claim 21, wherein b) in said method further comprises:

calculating a plurality of first derivatives of said plurality of Hough transforms for said plurality of discrete distances over said range of angles.

23. The computer system as described in claim 22, wherein c) in said method further comprises:

for each of said plurality of discrete distances, sorting out a maximum absolute slope value first derivative over said range of angles, said maximum absolute slope value first derivative corresponding to a local skew angle of an associated text line.

24. The computer system as described in claim 23, wherein said method further comprises:

calculating a global skew angle of said plurality of text lines of said first type; and

verifying slope angles corresponding to said set of maximum absolute slope values that are greater than said threshold value are associated with said plurality of text lines of a first type by comparing said slope angles to said global skew angle.

25. The computer system as described in claim 20, wherein d) in said method further comprises:

arranging said set of maximum absolute slope values of said plurality of slope values from minimum slope values to maximum slope values;

locating a first Gaussian distribution of associated with said plurality of text lines of a first type;

locating a second Gaussian distribution of said plurality of text lines of a second type; and

setting said threshold slope value between said first and second Gaussian distributions.

26. The computer system as described in claim 20, wherein d) in said method further comprises:

pairing said plurality of slope values to indicate x-height lines and baselines of said plurality of text lines.

27. The computer system as described in claim 20, wherein said method further comprises:

scanning said document to obtain a digital image of said document comprising a plurality of pixels, said scanning performed before said performing said plurality of projection profiles.

28. The computer system as described in claim 20, wherein said plurality of text lines of a first type comprise a plurality of text lines of machine printed text, and said plurality of text lines of a second type comprise a plurality of text lines of handwritten annotations.

29. The computer system as described in claim 20, wherein text lines of said first type are more uniform than text lines of said second type.