Document image processing method and system having function of determining body text region reading order

• US 5,907,631 A
• Filed: 06/02/1998
• Issued: 05/25/1999
• Est. Priority Date: 05/12/1993
• Status: Expired due to Term

• Current Assignee: Ricoh Company Limited
• Original Assignee: Ricoh Company Limited
• Inventors: Saitoh, Takashi
• Primary Examiner(s): Tran, Phuoc
• Application Number:
  US09/088,773
• Time in Patent Office: 357 Days
• Field of Search: 382/173, 382/176, 382/175, 382/224, 382/317
• US Class Current: 382/176
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/1444 Selective acquisition, locating or processing of specific regions, e.g. highlighted text, fiducial marks or predetermined fields
• CPC Class Codes: G06V 30/40 Document-oriented image-based pattern recognition
• CPC Class Codes: G06V 30/414 Extracting the geometrical structure, e.g. layout tree; Block segmentation, e.g. bounding boxes for graphics or text

Abstract

An extracting step extracts text regions from an input document image. A classifying step classifies the text regions into in-order reading regions to be successively read in the predetermined order and different-attribute regions. A detecting step detects the construction of the in-order reading regions. A determining step determines the reading order, in which the in-order reading regions are to be read, using the construction. The detecting step detects the construction in a manner that is the same whether the input document image comprises a vertically typeset document or a horizontally typeset document. The detecting step further includes a tree graph formation step c-1) forming a tree graph representing the construction including nodes respectively representing the in-order reading regions.

Claims

1. A computer-readable medium having stored thereon a plurality of sequences of instructions, said plurality of sequences of instructions including sequences of instructions which, when executed by a processor, cause said processor to:

a) extract text regions from an input document image;

b) classify said text regions into;

(b1) in-order reading regions of text which are to be successively read in a predetermined order and

(b2) different-attribute regions of text;

c) detect a construction of said in-order reading regions but not of said different-attribute regions; and

d) determine the reading order, in which said in-order reading regions are to be read, using said construction.

2. The computer-readable medium of claim 1, causing said processor to:

detect said construction in a manner that is the same whether said input document image comprises a vertically typeset document or a horizontally typeset document.

3. The computer-readable medium of claim 1, causing said processor to:

form a tree graph representing said construction including modes respectively representing said in-order reading regions.

4. The computer-readable medium of claim 1, causing said processor to:

classify said text regions into in-order reading regions enclosed by a box frame which is included in said input document image and in-order reading regions enclosed by no box frame; and

determine the reading order in which said in-order reading regions enclosed by a box frame are to be read and further determine the reading order in which said in-order reading regions enclosed by no box frame are to be read.

5. The computer-readable medium of claim 4, wherein:

said box frame is formed of four sides consisting of a top side, a bottom side, a right side and a left side.

6. The computer-readable medium of claim 1, causing said processor to:

e) check whether said reading order is correct or incorrect; and

f) re-determine the reading order if a result of incorrect is obtained.

7. The computer-readable medium of claim 6, wherein said check causes said processor to:

check the reading order, in which the in-order reading regions are to be read, for the in-order reading regions enclosed in a box frame which is included in said input document image; and

said re-determine causes said processor to re-determine the reading order for said in-order reading regions enclosed in said box frame.

8. The computer-readable medium of claim 7, wherein:

said box frame is formed of four sides consisting of a top side, a bottom side, a right side and a left side.

9. The computer-readable medium of claim 1, causing said processor to:

g) read the characters constituting said in-order reading regions in accordance with said reading order.

10. The computer-readable medium of claim 1, causing said processor to:

detect said construction using imaginary ruled lines, which may be generated depending on contents of an original image and then added to said original image so as to control the detection operation.

11. The computer-readable medium of claim 10, wherein said imaginary ruled lines are generated for blank regions having a predetermined shape/predetermined dimensions and/or for figure/table regions.

12. The computer-readable medium of claim 1, causing said processor to:

detect said construction using scopes of influence, assigned to appropriate regions, for searching subsequent regions; and

each of said scopes of influence assigned to a respective one of said appropriate regions represents a scope on which said respective one of said appropriate regions has influence.

13. The computer-readable medium of claim 1, causing said processor to:

prevent said different-attribute regions from affecting the determination of the reading order.

14. The computer-readable medium of claim 1, wherein said different-attribute regions include, a series of characters which are provided as footers and/or headers in said input document image.

15. A computer-readable medium having stored thereon a plurality of sequences of instructions, said plurality of sequences of instructions including sequences of instructions which, when executed by a processor, cause said processor to:

a) extract text regions from an input document image;

b) classify said text regions into in-order reading regions which are to be successively read in a predetermined order and into different-attribute regions;

c) detect a construction of said in-order reading regions;

d) determine the reading order, in which said in-order reading regions are to be read, using said construction;

e) check whether said reading order is correct or incorrect; and

f) re-determine the reading order if a result of incorrect is obtained;

wherein said check causes said processor to;

e1) provide reference points to the respective in-order reading regions;

e2) connect said reference points in accordance with a relevant reading order; and

e3) determine said reading order to be incorrect if lines formed as the result of the connection intersect.

16. A computer-readable medium having stored thereon a plurality of sequences of instructions, said plurality of sequences of instructions including sequences of instructions which, when executed by a processor, cause said processor to:

a) extract text regions from an input document image;

b) classify said text regions into in-order reading regions which are to be successively read in a predetermined order and into different-attribute regions;

c) detect a construction of said in-order reading regions;

d) determine the reading order, in which said in-order reading regions are to be read, using said construction;

e) check whether said reading order is correct or incorrect; and

f) re-determine the reading order if a result of incorrect is obtained;

wherein said check causes said processor to;

e1) provide reference points to the respective in-order reading regions;

e2) connect said reference points in accordance with a relevant reading order; and

e3) determine said reading order to be incorrect if a number of intersections of the lines formed as a result of the connection exceeds a predetermined value.

17. A computer-readable medium having stored thereon a plurality of sequences of instructions, said plurality of sequences of instructions including sequences of instructions which, when executed by a processor, cause said processor to:

a) extract text regions from an input document image;

b) classify said text regions into;

(b1) in-order reading regions of text which are to be read in a predetermined order and

(b2) different-attribute regions of text;

c) detect a construction of said in-order reading regions but not of said different-attribute regions; and

d) determine the reading order, in which said in-order reading regions are to be read, using said construction.

18. The computer-readable medium of claim 17, causing said processor to:

detect said construction in a manner that is the same whether said input document image comprises a vertically typeset document or a horizontally typeset document.

19. The computer-readable medium of claim 17, causing said processor to:

form a tree graph representing said construction including nodes respectively representing said in-order reading regions.

20. The computer-readable medium of claim 17, causing said processor to:

classify said text regions into in-order reading regions enclosed by a box frame which is included in said input document image and in-order reading regions enclosed by no box frame; and

determine the reading order of said in-order reading regions enclosed by a box frame and further determine the reading order of said in-order reading regions enclosed by no box frame.

21. The computer-readable medium of claim 20, wherein:

said box frame is formed of four sides consisting of a top side, a bottom side, a right side and a left side.

22. The computer-readable medium of claim 17, causing said processor to:

check whether said reading order is correct or incorrect; and

re-determine the reading order of said in-order reading regions using another predetermined procedure if a result of incorrect is obtained.

23. The computer-readable medium of claim 22, wherein said check causes said processor to:

check the reading order of the in-order reading regions for the in-order reading regions enclosed in a box frame which is included in said input document image; and

said re-determine causes said processor to re-determine the reading order for said in-order reading regions enclosed in said box frame.

24. The computer-readable medium of claim 23, wherein:

said box frame is formed of four sides consisting of a top side, a bottom side, a right side and a left side.

25. The computer-readable medium of claim 17, causing said processor to read the characters constituting said in-order reading regions in accordance with said reading order.

26. The computer-readable medium of claim 17, causing said processor to:

detect said construction using imaginary ruled lines, which may be generated depending on contents of an original image and then added to said original image so as to control the detection operation.

27. The computer-readable medium of claim 26, wherein said imaginary ruled lines are generated for blank regions having a predetermined shape/predetermined dimensions and/or for figure/table regions.

28. The computer-readable medium of claim 17, causing said processor to:

detect said construction using scopes of influence, assigned to appropriate regions, for searching subsequent regions; and

each of said scopes of influence assigned to a respective one of said appropriate regions represents a scope on which said respective one of said appropriate regions has influence.

29. The computer-readable medium of claim 17, causing said processor to:

prevent said different-attribute regions from affecting the determination of said reading order.

30. The computer-readable medium of claim 17, wherein said different-attribute regions include:

a series of characters which are provided as footers and/or headers in said input document image.

31. A computer-readable medium having stored thereon a plurality of sequences of instructions, said plurality of sequences of instructions including sequences of instructions which, when executed by a processor, cause said processor to:

a) extract text regions from an input document image;

b) classify said text regions into in-order reading regions which are to be read in a predetermined order and into different-attribute regions;

c) detect a construction of said in-order reading regions;

d) determine the reading order, in which said in-order reading regions are to be read, using said construction;

e) check whether said reading order is correct or incorrect; and

f) re-determine the reading order of said in-order reading regions using another predetermined procedure if a result of incorrect is obtained;

wherein said check causes said processor to;

e1) provide reference points to the respective in-order reading regions;

e2) connect said reference points in accordance with a relevant reading order; and

e3) determine said reading order to be incorrect if lines formed as the result of the connection intersect.

32. A computer-readable medium having stored thereon a plurality of sequences of instructions, said plurality of sequences of instructions including sequences of instructions which, when executed by a processor, cause said processor to:

a) extract text regions from an input document image;

b) classify said text regions into in-order reading regions which are to be read in a predetermined order and into different-attribute regions;

c) detect a construction of said in-order reading regions;

d) determine the reading order, in which said in-order reading regions are to be read, using said construction;

e) check whether said reading order is correct or incorrect; and

f) re-determine the reading order of said in-order reading regions using another predetermined procedure if a result of incorrect is obtained;

wherein said check causes said processor to;

e1) provide reference points to the respective in-order reading regions;

e2) connect said reference points in accordance with a relevant reading order; and

e3) determine said reading order to be incorrect if intersections of lines formed as the result of the connection exceeds a predetermined threshold value.

33. A computer-readable medium having stored thereon a plurality of sequences of instructions, said plurality of sequences of instructions including sequences of instructions which, when executed by a processor, cause said processor to:

a) extract text regions from an input document image;

b) classify said text regions into;

(b1) body regions of text which are to be successively read in a predetermined order and

(b2) different-attribute regions of text;

c) detect a construction of said body regions but not of said different-attribute regions; and

d) determine the reading order, in which said body regions are to be read, using said construction.