E-mail signature block analysis

• US 6,373,985 B1
• Filed: 08/12/1998
• Issued: 04/16/2002
• Est. Priority Date: 08/12/1998
• Status: Expired due to Term

• Current Assignee: Nokia of America Corporation (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Chen, Hao, Sproat, Richard W., Hu, Jianying
• Primary Examiner(s): Johns, Andrew W.
• Assistant Examiner(s): AZARIAN, SEYED H
• Application Number:
  US09/132,682
• Time in Patent Office: 1,343 Days
• Field of Search: 382/229, 382/230, 382/231, 382/232, 382/226, 382/227, 704/9, 704/258, 704/259, 704/260, 704/269
• US Class Current: 382/229
• CPC Class Codes: G06V 30/414 Extracting the geometrical structure, e.g. layout tree; Block segmentation, e.g. bounding boxes for graphics or text
• CPC Class Codes: G06V 30/416 Extracting the logical structure, e.g. chapters, sections or page numbers; Identifying elements of the document, e.g. authors

Abstract

A technique analyzing loosely constrained text blocks, such as e-mail signature blocks by performing a two-dimensional geometrical analysis and a one-dimensional language analysis in order to classify sub-blocks at the loosely constrained text block into particular functional classes. The present technique may also be utilized to identify a personal name from a user name in a loosely constrained text block, such as an e-mail signature block.

Claims

1. A method of analyzing a loosely constrained text block, comprising the steps of:

performing a two-dimensional geometrical analysis to divide the loosely constrained text block into reading blocks;

performing a one-dimensional language analysis on the reading blocks to divide the reading blocks into functional blocks; and

classifying each of functional blocks as belonging to a functional class.

2. The method of claim 1, wherein said method is a preprocess performed in e-mail text-to-speech rendering.

3. The method of claim 1, wherein the loosely constrained text block is an e-mail message signature block.

4. The method of claim 1, wherein the two-dimensional geometric analysis includes the steps of line segment extraction and connected component analysis on foreground characters in the loosely constrained text block to produce the reading blocks.

5. The method of claim 1, wherein the one-dimensional language analysis includes the steps of cost estimating to produce an input weighted finite state transducer, composing the input weighted finite state transducers with lexical and grammatical weighted finite state transducers, performing a bestpath search to identify a bestpath weighted finite state transducer and decoding the bestpath weighted finite state transducer into the functional blocks.

6. The method of claim 4, wherein the two-dimensional geometric analysis further includes the steps of line segment extraction and connected component analysis on background characters in the loosely constrained text block to ensure the reading blocks include no mixed reading blocks.

7. The method of claim 5, wherein the cost estimating step includes expression matching for strict classes and implementing commonly observed conventions for loose classes.

8. A method of automatically identifying a personal name from a user name in a loosely constrained text block, comprising the steps of:

constructing a single path finite state acceptor which generates the user name;

constructing a well-formed user name finite state acceptor for a candidate phrase in the loosely constrained text block;

composing the single path finite state acceptor with the well-formed user name finite state acceptor to produce a resulting finite state acceptor; and

identifying the candidate phrase as the personal name if the resulting finite state acceptor is non-empty.

9. The method of claim 8, wherein said method is part of a preprocess performed in e-mail text-to-speech rendering.

10. The method of claim 8, wherein the loosely constrained text block is an e-mail message signature block and the user name is a name portion of an e-mail address.

11. A processor for analyzing a loosely constrained text block, comprising:

a two-dimensional geometrical analysis processing unit for dividing the loosely constrained text block into reading blocks;

a one-dimensional language analysis processing unit for dividing the reading blocks into functional blocks; and

a classifying processor unit for classifying each of functional blocks as belonging to a functional class.

12. The processor of claim 11, wherein said processor is a preprocessor used in e-mail text-to-speech rendering.

13. The processor of claim 11, wherein the loosely constrained text block is an e-mail message signature block.

14. The processor of claim 11, wherein the two-dimensional geometric analysis processor unit includes a line segment extraction processing unit and a connected component analysis processing unit for performing line segment extraction and a connected component analysis on foreground characters in the loosely constrained text block to produce the reading blocks.

15. The processor of claim 11, wherein the one-dimensional language analysis processing unit includes a cost estimating processing unit for producing an input weighted finite state transducer, a composing processor unit for composing the input weighted finite state transducers with lexical and grammatical weighted finite state transducers, a bestpath search processing unit for identifying a bestpath weighted finite state transducer and a decoding processing unit for decoding the bestpath weighted finite state transducer into the functional blocks.

16. The processor of claim 14, wherein the two-dimensional geometric analysis processing unit further includes a line segment extraction processing unit and a connected component analysis processing unit for performing line segment extraction and connected component analysis on background characters in the loosely constrained text block to ensure the reading blocks include no mixed reading blocks.

17. The processor of claim 15, wherein the cost estimating processing unit performs expression matching for strict classes and implements commonly observed conventions for loose classes.

18. A process or for automatically identifying a personal name from a user name in a loosely constrained text block, comprising:

a first processing unit for constructing a single path finite state acceptor which generates the user name;

a second processing unit for constructing a well-formed user name finite state acceptor for a candidate phrase in the loosely constrained text block;

a third processing unit for composing the single path finite state acceptor with the well-formed user name finite state acceptor to produce a resulting finite state acceptor; and

a fourth processing unit for identifying the candidate phrase as the personal name if the resulting finite state acceptor is non-empty.

19. The processor of claim 18, wherein said processor is a preprocessor performed in e-mail text-to-speech rendering.

20. The processor of claim 18, wherein the loosely constrained text block is an e-mail message signature block and the user name is a name portion of an e-mail address.

21. A computer program embodied on a computer-readable medium for analyzing a loosely constrained text block, comprising:

a two-dimensional geometrical analysis source code segment for dividing the loosely constrained text block into reading blocks;

a one-dimensional language analysis source code segment for dividing the reading blocks into functional blocks; and

a classifying source code segment for classifying if each of functional blocks as belonging to a functional class.

22. The computer program of claim 21, wherein said computer program is a preprocess performed in e-mail text-to-speech rendering.

23. The computer program of claim 21, wherein the loosely constrained text block is an e-mail message signature block.

24. The computer program of claim 21, wherein the two-dimensional geometric analysis source code segment includes a line segment extraction source code segment and a connected component analysis source code segment for performing line segment extraction and connected component analysis on foreground characters in the loosely constrained text block to produce the reading blocks.

25. The computer program of claim 21, wherein the one-dimensional language analysis source code segment includes a cost estimating source code segment for producing an input weighted finite state transducer, a composing source code segment for composing the input weighted finite state transducers with lexical and grammatical weighted finite state transducers, a bestpath search source code segment for identifying a bestpath weighted finite state transducer and a decoding source code segment for decoding the bestpath weighted finite state transducer into the functional blocks.

26. The computer program of claim 24, wherein the two-dimensional geometric analysis source code segment further includes a line segment extraction source code segment and a connected component analysis source code segment for performing line segment extraction and connected component analysis on background characters in the loosely constrained text block to ensure the reading blocks include no mixed reading blocks.

27. The computer program of claim 25, wherein the cost estimating source code segment performing expression matching for strict classes and implements commonly observed conventions for loose classes.

28. A computer program embodied in a computer readable medium for automatically identifying a personal name from a user name in a loosely constrained text block, comprising:

a first source code segment for constructing a single path finite state acceptor which generates the user name;

a second source code segment for constructing a well-formed user name finite state acceptor for a candidate phrase in the loosely constrained text block;

a third source code segment for composing the single path finite state acceptor with the well-formed user name finite state acceptor to produce a resulting finite state acceptor; and

a fourth source code segment for identifying the candidate phrase as the personal name if the resulting finite state acceptor is non-empty.

29. The computer program of claim 28, wherein said computer program is part of a preprocess performed in e-mail text-to-speech rendering.

30. The computer program of claim 28, wherein the loosely constrained text block is an e-mail message signature block and the user name is a name portion of an e-mail address.

31. A computer data signal for analyzing a loosely constrained text block, comprising:

a two-dimensional geometrical analysis signal segment for dividing the loosely constrained text block into reading blocks;

a one-dimensional language analysis signal segment for dividing the reading blocks into functional blocks; and

a classifying signal segment for classifying each of functional blocks as belonging to a functional class.

32. The computer data signal of claim 31, wherein said computer data signal executes a preprocess performed in e-mail text-to-speech rendering.

33. The computer data signal of claim 31, wherein the loosely constrained text block is an e-mail message signature block.

34. The computer data signal of claim 31, wherein the two-dimensional geometric analysis signal segment includes a line segment extraction signal segment and a connected component analysis signal segment for performing line segment extraction and connected component analysis on foreground characters in the loosely constrained text block to produce the reading blocks.

35. The computer data signal of claim 31, wherein the one-dimensional language analysis signal segment includes a cost estimating signal segment for producing an input weighted finite state transducer, a composing signal segment for composing the input weighted finite state transducers with lexical and grammatical weighted finite state transducers, a bestpath search signal segment for identifying a bestpath weighted finite state transducer and a decoding signal segment for decoding the bestpath weighted finite state transducer into the functional blocks.

36. The computer data signal of claim 34, wherein the two-dimensional geometric analysis signal segment further includes a line segment extraction signal segment and a connected component analysis signal segment for performing line segment extraction and connected component analysis on background characters in the loosely constrained text block to ensure the reading blocks include no mixed reading blocks.

37. The computer data signal of claim 35, wherein the cost estimating signal segment performs expression matching for strict classes and implements commonly observed conventions for loose classes.

41. The computer data signal of claim 31, wherein said computer data signal is embodied in a carrier wave.

38. A computer data signal for automatically identifying a personal name from a user name in a loosely constrained text block, comprising:

a first signal segment for constructing a single path finite state acceptor which generates the user name;

a second signal segment for constructing a well-formed user name finite state acceptor for a candidate phrase in the loosely constrained text block;

a third signal segment for composing the single path finite state acceptor with the well-formed user name finite state acceptor to produce a resulting finite state acceptor; and

a fourth signal segment for identifying the candidate phrase as the personal name if the resulting finite state acceptor is non-empty.

39. The computer data signal of claim 38, wherein said computer data signal executes a preprocess performed in e-mail text-to-speech rendering.

40. The computer data signal of claim 38, wherein the loosely constrained text block is an e-mail message signature block and the user name is a name portion of an e-mail address.

42. The computer data signal of claim 38, wherein said computer data signal is embodied in a carrier wave.