Automatic method of identifying sentence boundaries in a document image

• US 5,892,842 A
• Filed: 12/14/1995
• Issued: 04/06/1999
• Est. Priority Date: 12/14/1995
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Bloomberg, Dan S.
• Primary Examiner(s): Coles, Edward L.
• Assistant Examiner(s): Lee, Cheukfan
• Application Number:
  US08/572,597
• Time in Patent Office: 1,209 Days
• Field of Search: 382/173, 382/177, 382/179, 382/229, 382/187, 382/203, 382/181, 382/308, 382/256, 382/175, 382/190, 395/144, 395/145, 395/146
• US Class Current: 382/173
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/146 Aligning or centring of the image pick-up or image-field

Abstract

A method of automatically identifying sentence boundaries in a document image without performing character recognition to generate an ASCII representation of the document text. The identification process begins by selecting a connected component from the multiplicity of connected components of a text line. Next, it is determined whether the selected connected component might represent a period based upon its shape. If the selected connected component is dot shaped, then it is determined whether the selected connected component might represent a colon. Finally, if the selected connected component is dot shaped and not part of a colon, the selected connected component is labeled as a sentence boundary.

Claims

1. A method of identifying sentence boundaries within a document image without performing character recognition, the document image including a multiplicity of connected components, each connected component having a bounding box, the method being implemented by a processor coupled to a memory storing instructions representing the method, the method comprising the steps of:

a) selecting a connected component from the multiplicity of connected components;

b) determining whether the selected connected component might represent a period based upon a shape of the selected connected component;

c) determining whether the selected connected component might represent a colon; and

d) labeling the selected connected component as a sentence boundary if the selected connected component might be a period and is not part of a colon.

2. The method of claim 1 wherein step b) comprises the steps of:

a) determining whether the bounding box of the selected connected component is too small to represent a period;

b) determining whether the bounding box of the selected connected component is dot shaped; and

c) determining whether the bounding box of the selected connected component is close enough to a baseline associated with the selected connected component.

3. The method of claim 1 wherein step c) comprises the steps of:

a) determining whether either of a pair of connected components neighboring the selected connected component are dot shaped;

b) determining whether either bounding box of the pair of connected components neighboring the selected connected component overlap horizontally with the bounding box associated with the selected connected component; and

c) determining whether a distance between the bounding box of the selected connected component and either box of the pair of connected components neighboring the selected connected component is less than a first threshold.

4. The method of claim 1 further comprising the step of:

e) determining whether the selected connected component is part of an intra-sentence abbreviation; and

wherein during step d) the selected connected component is not labeled as a sentence boundary if the selected connected component is part of an intra-sentence abbreviation.

5. The method of claim 4 wherein step e) comprises the step of:

1) determining whether a following connected component is too close to the selected connected component.

6. The method of claim 4 wherein step e) comprises the step of:

1) determining whether a following connected component is a capital letter.

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

f) determining whether the selected connected component is part of an ellipsis; and

wherein during step d) the selected connected component is not labeled as a sentence boundary if the selected connected component is part of an ellipsis.

8. The method of claim 7 wherein step f) comprises the steps of:

a) determining whether a following connected component is dot shaped; and

b) determining whether the following connected component is close to a baseline associated with the selected connected component.

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

g) determining whether the selected connected component is part of an exclamation mark or a question mark; and

wherein during step d) further comprises labeling the selected connected component as the sentence boundary if the selected connected component is part of a question mark or exclamation mark.

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

g) determining whether a following connected component represents a quotation mark; and

f) labeling the following connected component as a sentence boundary if the following connected component represents a quotation mark.

11. The method of claim 10 wherein step g) comprises the steps of:

a) determining whether a bounding box of a following connected component is quote shaped;

b) determining whether the bounding box of the following connected component is high enough above the connected component;

c) determining whether the bounding box of the following connected component is close enough to the selected connected component to be part of the same sentence.

12. The method of claim 7 wherein step c) comprises the steps of:

1) determining whether either of a pair of connected components neighboring the selected connected component are dot shaped;

2) determining whether either bounding box of the pair of connected components neighboring the selected connected component overlap horizontally with the bounding box associated with the connected component; and

3) determining whether a distance between the bounding box of the selected connected component and either box of the pair of connected components neighboring the selected connected component is less than a first threshold.

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

g) determining whether the selected connected component is part of an exclamation mark or a question mark; and

wherein during step d) further comprises labeling the selected connected component as the sentence boundary if the selected connected component is part of a question mark or exclamation mark.

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

g) determining whether a following connected component represents a quotation mark; and

f) labeling the following connected component as a sentence boundary if the following connected component represents a quotation mark.

15. The method of claim 14 wherein step g) comprises the steps of:

a) determining whether a bounding box of the following connected component is quote shaped;

b) determining whether the bounding box of the following connected component is high enough above the selected connected component;

c) determining whether the bounding box of the following connected component is close enough to the selected connected component to be part of the same sentence.

16. A method of identifying sentence boundaries within a document image without performing character recognition, the document image including a multiplicity of connected components, each connected component having a bounding box, the method being implemented by a processor coupled to a memory storing instructions representing the method, the method comprising the steps of:

a) selecting a connected component from the multiplicity of connected components;

b) determining whether the selected connected component might be a period based upon a shape of the selected connected component;

c) determining whether the selected connected component is part of a colon;

d) determining whether the selected connected component is part of an ellipsis;

e) determining whether the selected connected component is part of an exclamation mark or a question mark;

f) determining whether the selected connected component is part of an intra-sentence abbreviation; and

g) labeling the selected connected component as a sentence boundary if the selected connected component might be a period, is not part of a colon, is not part of an ellipsis, is not part of a question mark or exclamation mark, and is not part of an intra-sentence abbreviation.

17. The method of claim 16 wherein step b) comprises the steps of:

1) determining whether the bounding box of the selected connected component is too small for the selected connected component to be a period;

2) determining whether the shape of the bounding of the selected connected component is dot shaped; and

3) determining whether the bounding box of the selected connected component is too close to a baseline associated with the selected connected component.

18. The method of claim 16 wherein step c) comprises the steps of:

1) determining whether either of a pair of connected components neighboring the selected connected component are dot shaped;

2) determining whether either bounding box of the pair of connected components neighboring the selected connected component overlap the bounding box of the selected connected component; and

3) determining whether a distance between the bounding box of the selected connected component and either box of the pair of connected components neighboring the selected connected component is less than a first threshold.

19. The method of claim 16 wherein step f) comprises the step of:

1) determining whether a following connected component is close enough to the selected connected component.

20. The method of claim 16 wherein step f) comprises the step of:

1) determining the following connected component is a capital letter.

21. The method of claim 16 wherein step c) comprises the steps of:

1) determining whether either of a pair of connected components neighboring the selected connected component are dot shaped;

2) determining whether either bounding box of the pair of connected components neighboring the selected connected component overlap with the bounding box of the selected connected component; and

3) determining whether a distance between the bounding box of the selected connected component and either box of the pair of connected components neighboring the selected connected component is less than a first threshold.

22. The method of claim 21 wherein step f) comprises the step of:

1) determining whether a following connected component is close enough to the selected connected component.

23. The method of claim 22 wherein step f) comprises the steps of:

1) determining whether the following connected component is a capital letter.

24. An article of manufacture comprising:

a) a memory; and

b) instructions stored in the memory for a method of identifying sentence boundaries within a document image without performing character recognition, the document image including a multiplicity of connected components, each connected component representing a character and having a bounding box, the method being implemented by a processor coupled to the memory, the method including the steps of;

1) selecting a connected component from the multiplicity of connected components, each connected component;

2) determining whether the selected connected component might be a period based upon a shape of the selected connected component;

3) determining whether the selected connected component is part of a colon;

4) determining whether the selected connected component is part of an ellipsis;

5) determining whether the selected connected component is part of an exclamation mark or a question mark;

6) determining whether the selected connected component is part of an intra-sentence abbreviation; and

7) labeling the selected connected component as a sentence boundary if the connected component might be a period, is not part of a colon, is not part of an ellipsis, is not part of a question mark or exclamation mark, and is not part of an intra-sentence abbreviation.