Ordering groups of text in an image

Details Ordering groups of text in an image Ordering groups of text in an image

1997-12-30

2001-01-16

Feild, Joseph H. (Department: 2776)

Data processing: database and file management or data structures

Database design

Data structure types

C382S180000

Reexamination Certificate

active

06175844

ABSTRACT:

BACKGROUND
The invention relates to ordering groups of text in an image.
Paper documents can be scanned and stored as images in a computer. Text recognition techniques, such as optical character recognition (OCR), can then be used to convert text in these images to a computer-editable format, such as ASCII characters. Scanned images can contain text organized in multiple, distinct blocks (e.g., multiple columns of text, headlines, captions, footnotes, footers). The text blocks may further be separated by relatively large areas of blank space and graphical objects (lines, pictures, and so forth). Text can also be surrounded by a frame or contain insets, which further separate the text into blocks. Although a person reading the page may be able to recognize the proper order of the text blocks in the image, it may be difficult for an OCR program to identify the text (by discarding the non-text components such as blank spaces and graphical objects) and then group the text into the proper reading order.
SUMMARY
In general, in one aspect, the invention features a computer-implemented method of ordering text in an image stored in a computer. Text is grouped in multiple regions. The text regions are represented as a graph having vertices and edges. An optimal Hamiltonian path through the vertices is calculated, and the text regions are ordered according to the calculated optimal Hamiltonian path.
Implementations of the invention may include one or more of the following features. The representing step includes defining each group of text as a vertex in a graph, defining edges between the vertices, and assigning weights to the edges. Directed pairs of edges are defined between any two vertices. An optimal Hamiltonian path through the vertices is calculated based on the assigned edge weights by solving a traveling salesman problem. The weights assigned the edges between the vertices are based on the distance between any two text regions, the characteristics of the corresponding text regions, and the existence of non-text separators between text regions.
In general, in another aspect, the invention features a program residing on a computer-readable medium for ordering text in an image stored in a computer. The program includes instructions for causing the computer to group the text in multiple regions and to represent the text regions as a graph having vertices and edges. The text regions are ordered according to a calculated optimal Hamiltonian path through the vertices.
In general, in another aspect, the invention features an apparatus for recognizing text in an image that includes a storage medium to store the image and a processor operatively coupled to the storage medium. The processor is configured to group the text in multiple regions and to represent the text regions as a graph having vertices and edges. Further, the text regions are ordered according to a calculated optimal Hamiltonian path through the vertices.
The invention has one or more of the following advantages. The proper order of multiple, distinct blocks of text in a captured image can be determined reliably by a text capture program.
Other features and advantages of the invention will become apparent from the following description and from the claims.


REFERENCES:
patent: 4935877 (1990-06-01), Koza
patent: 5185813 (1993-02-01), Tsujimoto
patent: 5666469 (1997-09-01), Lee
patent: 5669007 (1997-09-01), Tateishi
patent: 5955322 (1999-09-01), Guarnieri et al.
Saitoh et al, “Document Image Segmentation and Text Ordering”, Proceedings of the Second International Conference on Document Analysis and Recognition, pp. 323-329, 1993.
Hao et al, “Nested Segmentation: An Approach for Layout Analysis in Document Classification”, Proceedings of the Second International Conference on Document Analysis and Recognition, pp. 319-322, 1993.
Taylor et al, “An Intelligent Document Understanding System”, Proceedings of the Second International Conference on Document Analysis and Recognition, pp. 107-110, 1993.
Belaid et al, “A Labeling Approach for Mixed Document Blocks”, Proceedings of the Second International Conference on Document Analysis and Recognition, pp. 749-752, 1993.
Itonori, “Table Structure Recognition Based on Textblock Arrangement and Ruled Line Position”, Proceedings of the Second International Conference on Document Analysis and Recognition, pp. 765-768, 1993.
Iwane et al, “A Functional Classification Approach to Layout Analysis of Document Images”, Proceedings of the Second International Conference on Document Analysis and Recognition, pp. 778-781, 1993.
Ito et al., “Field Segmentation and Classification in Document Image,” Proceedings of the 6th International Conference on Pattern Recognition, Munich, pp. 492-495, vol. 1, Oct. 19-22, 1982, IEEE.
Balestri et al., “A Method for The Correct Ordering of Typewritten Lines,” Signal processing: Theories and Applications, Grenoble, Sep. 5-8, 1988, vol. 3, pp. 1609-1611.
ExperVision, TypeReader User's Guide, Chapter 7: Locating, Text Regions, and Templates, pp. 71-90 (Jun. 1992).

Affiliated with

Also associated with

Rating

Ordering groups of text in an image does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Ordering groups of text in an image, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Ordering groups of text in an image will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2542002