Document layout analysis - Knowledge (XXG)

22: 157:

advantage that they parse the global structure of a document directly, thus eliminating the need to iteratively cluster together the possibly hundreds or even thousands of characters/symbols which appear on a document. They tend to be faster, but in order for them to operate robustly they typically require a number of assumptions to be made about on the layout of the document. Examples of top-down approaches include the recursive X-Y cut algorithm, which decomposes the document in rectangular sections.

156:

The bottom-up approaches are the traditional ones, and they have the advantage that they require no assumptions on the overall structure of the document. On the other hand, bottom-up approaches require iterative segmentation and clustering, which can be time consuming. Top-down approaches have the

209:

where k is an integer greater than or equal to four. O`Gorman suggests k=5 in his paper as a good compromise between robustness and speed. The reason to use at least k=4 is that for a symbol in a document, the two or three nearest symbols are the ones right next to it on the same text line. The

230:

For each symbol, look at its nearest neighbors and flag any of them that are a distance away which is within some tolerance of the between-character spacing distance or between-word spacing distance. For each nearest neighbor symbol which is flagged, draw a line segment connecting their

148:

approaches which iteratively parse a document based on the raw pixel data. These approaches typically first parse a document into connected regions of black and white, then these regions are grouped into words, then into text lines, and finally into text blocks. Secondly, there are

262:– A free document layout analysis and OCR system, implemented in C++ and Python and for FreeBSD, Linux, and Mac OS X. This software supports a plug-in architecture which allows the user to select from a variety of different document layout analysis and OCR algorithms. 241:

For each pair of text lines, one can compute a minimum distance between their corresponding line segments. If this distance is within some tolerance of the between-line spacing calculated in step 7, then the two text lines are grouped into the same

238:. Using all the centroids in a text line, one can compute an actual line segment representing the text line with linear regression. This is important because it is unlikely that all the centroids of symbols in a text line are actually collinear. 213:

Each nearest neighbor pair of symbols is related by a vector pointing from one symbol’s centroid to the other symbol’s centroid. If these vectors are plotted for every pair of nearest neighbor symbols, then one gets what is called the

226:

The nearest-neighbor distance histogram has several peaks, and these peaks typically represent between-character spacing, between-word spacing, and between-line spacing. Calculate these values from the histogram and set them

222:

Using the nearest-neighbor angle histogram, the skew of the document can be calculated. If the skew is acceptably low, continue to the next step. If it is not, rotate the image so as to remove the skew and return to step

98:

image of a text document. A reading system requires the segmentation of text zones from non-textual ones and the arrangement in their correct reading order. Detection and labeling of the different zones (or blocks) as

172:

algorithms that the characters in the document image are oriented so that text lines are horizontal. Therefore, if there is skew present then it is important to rotate the document image so as to remove it.

218:

for the document (See figure below). One can also use the angle Θ from the horizontal and distance D between two nearest neighbor symbols and create a nearest-neighbor angle and nearest-neighbor distance

168:. Skew refers to the fact that a document image may be rotated in a way so that the text lines are not perfectly horizontal. It is a common assumption in both document layout analysis algorithms and 610: 735: 464:

Cattoni, R.; Coianiz, T.; Messelodi, S.; Modena, C. M. "Geometric Layout Analysis Techniques for Document Image Understanding: a Review. ITC-irst Technical Report TR#9703-09".

188:

Preprocess the image to remove Gaussian and salt-and-pepper noise. Note that some noise removal filters may consider commas and periods as noise, so some care must be taken.

184:

In this section we will walk through the steps of a bottom-up document layout analysis algorithm developed in 1993 by O`Gorman. The steps in this approach are as follows:

210:

fourth-nearest symbol is typically on a line right above or below, and it is important to include these symbols in the nearest neighbor calculation for the following.

176:

It follows that the first steps in any document layout analysis code are to remove image noise and to come up with an estimate for the skew angle of the document.

268:– An OCR suite for Linux, written in python, which also supports document layout analysis. This software is actively being developed, and is free and open-source. 130: 126:

engine, but it can be used also to detect duplicate copies of the same document in large archives, or to index documents by their structure or pictorial content.

300: 115:. But text zones play different logical roles inside the document (titles, captions, footnotes, etc.) and this kind of semantic labeling is the scope of the 603: 761: 596: 43: 122:

Document layout analysis is the union of geometric and logical labeling. It is typically performed before a document image is sent to an

694: 65: 153:

approaches which attempt to iteratively cut up a document into columns and blocks based on white space and geometric information.

160:

There are two issues common to any approach at document layout analysis: noise and skew. Noise refers to image noise, such as

619: 206: 169: 123: 83: 307:

Geometric Layout Analysis Techniques for Document Image Understanding: a Review, ITC-irst Technical Report TR#9703-09

306: 36: 30: 283: 133: 756: 47: 249:

Finally, one can calculate a bounding box for each text block, and the document layout analysis is complete.

542: 436: 341:

Simon, A.; Pret, J.-C.; Johnson, A.P. (1997). "A fast algorithm for bottom-up document layout analysis".

469: 392: 161: 108: 671: 661: 636: 547: 441: 278: 579:

Proceedings of the Third International Conference on Document Analysis and Recognition (ICDAR '95)

91: 684: 679: 552: 508: 446: 371: 350: 329: 533:

Seong-Whan Lee; Dae-Seok Ryu (2001). "Parameter-free geometric document layout analysis".

482: 405: 362:

Seong-Whan Lee; Dae-Seok Ryu (2001). "Parameter-free geometric document layout analysis".

301:

High Performance Document Layout Analysis by Thomas M. Breuel, at PARC, Palo Alto, CA, USA

79: 588: 165: 750: 628: 95: 104: 689: 288: 571: 709: 144:

There are two main approaches to document layout analysis. Firstly, there are

100: 651: 384: 265: 198:

Segment the image into connected components of black pixels. These are the

714: 704: 699: 195:, i.e. convert each pixel value to completely white or completely black. 719: 656: 499:

O'Gorman, L. (1993). "The document spectrum for page layout analysis".

385:"ANASTASIL: hybrid knowledge-based system for document layout analysis" 320:

O'Gorman, L. (1993). "The document spectrum for page layout analysis".

259: 556: 512: 375: 354: 333: 450: 202:

of the image. For each symbol, compute a bounding box and centroid.

646: 129:

Document layout is formally defined in the international standard

641: 572:"Recursive X-Y Cut using Bounding Boxes of Connected Components" 592: 427:

Baird, K.S. (July 1992). "Anatomy of a versatile page reader".

535: