Document Layout Analysis Document Layout Analysis repos for development with PdfPig.

Definition

From wikipedia: Document layout analysis is the process of identifying and categorizing the regions of interest in the scanned 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 text body, illustrations, math symbols, and tables embedded in a document is called geometric layout analysis. 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 logical layout analysis.

In this repos, we will not considere scanned documents, but classic pdf documents and leverage all available information (e.g. letters bounding boxes, fonts).

Resources

Text extraction

High precision text extraction from PDF documents | Øyvind Raddum Berg
User-Guided Information Extraction from Print-Oriented Documents | Tamir Hassan
Combining Linguistic and Spatial Information for Document Analysis | Aiello, Monz and Todoran
New Methods for Metadata Extraction from Scientific Literature | Dominika Tkaczyk
A System for Converting PDF Documents into Structured XML Format | Hervé Déjean, Jean-Luc Meunier
Layout and Content Extraction for PDF Documents | Hui Chao, Jian Fan
DocParser: Hierarchical Structure Parsing of Document Renderings | J. Rausch, O. Martinez, F. Bissig, C. Zhang, and S. Feuerriegel

Page segmentation

Performance Comparison of Six Algorithms for Page Segmentation | Faisal Shafait, Daniel Keysers, and Thomas M. Breuel
A Fast Algorithm for Bottom-Up Document Layout Analysis | Anikó Simon, Jean-Christophe Pret, and A. Peter Johnson
Empirical Performance Evaluation Methodology and its Application to Page Segmentation Algorithms: A Review | Pinky Gather, Avininder Singh
Layout Analysis based on Text Line Segment Hypotheses | Thomas M. Breuel
Hybrid Page Layout Analysis via Tab-Stop Detection | Ray Smith
Extending the Page Segmentation Algorithms of the Ocropus Documentation Layout Analysis System | Amy Alison Winder
Object-Level Document Analysis of PDF Files | Tamir Hassan
Document Image Segmentation as a Spectral Partitioning Problem | Dasigi, Jain and Jawahar
Benchmarking Page Segmentation Algorithms | S. Randriamasy, L. Vincent

Recursive XY Cut `implementation`

The X-Y cut segmentation algorithm, also referred to as recursive X-Y cuts (RXYC) algorithm, is a tree-based top-down algorithm. The root of the tree represents the entire document page. All the leaf nodes together represent the final segmentation. The RXYC algorithm recursively splits the document into two or more smaller rectangular blocks which represent the nodes of the tree. At each step of the recursion, the horizontal and vertical projection profiles of each node are computed. Then, the valleys along the horizontal and vertical directions, VX and VY, are compared to corresponding predefined thresholds TX and TY. If the valley is larger than the threshold, the node is split at the mid-point of the wider of VX and VY into two children nodes. The process continues until no leaf node can be split further. Then, noise regions are removed using noise removal thresholds TnX and TnY. [source]

Recursive X-Y Cut using Bounding Boxes of Connected Components | Jaekyu Ha, Robert M. Haralick and Ihsin T. Phillips

Docstrum `implementation`

The Docstrum algorithm by Gorman is a bottom-up approach based on nearest-neighborhood clustering of connected components extracted from the document image. After noise removal, the connected components are separated into two groups, one with dominant characters and another one with characters in titles and section heading, using a character size ratio factor fd. Then, K nearest neighbors are found for each connected component. Then, text-lines are found by computing the transitive closure on within-line nearest neighbor pairings using a threshold ft. Finally, text-lines are merged to form text blocks using a parallel distance threshold fpa and a perpendicular distance threshold fpe. source

The Document Spectrum for Page Layout Analysis | Lawrence O’Gorman
Document Structure and Layout Analysis | Anoop M. Namboodiri and Anil K. Jain
Document Layout Analysis | Garrett Hoch

Voronoi

The Voronoi-diagram based segmentation algorithm by Kise et al. is also a bottom-up algorithm. In the first step, it extracts sample points from the boundaries of the connected components using a sampling rate sr. Then, noise removal is done using a maximum noise zone size threshold nm, in addition to width, height, and aspect ratio thresholds. After that the Voronoi diagram is generated using sample points obtained from the borders of the connected components. Superfluous Voronoi edges are deleted using a criterion involving the area ratio threshold ta, and the inter-line spacing margin control factor fr. Since we evaluate all algorithms on document pages with Manhattan layouts, a modified version of the algorithm is used to generate rectangular zones.source

Voronoi++: A Dynamic Page Segmentation approach based on Voronoi and Docstrum features | Mudit Agrawal and David Doermann

Constrained text-line detection

The layout analysis approach by Breuel finds text-lines as a two step process:

Find tall whitespace rectangles and evaluate them as candidates for gutters, column separators, etc. The algorithm for finding maximal empty whitespace is described in Breuel. The whitespace rectangles are returned in order of decreasing quality and are allowed a maximum overlap of Om.
The whitespace rectangles representing the columns are used as obstacles in a robust least square, globally optimal text-line detection algorithm. Then, the bounding box of all the characters making the text-line is computed. The method was merely intended by its author as a demonstration of the application of two geometric algorithms, and not as a complete layout analysis system; nevertheless, we included it in the comparison because it has already proven useful in some applications. It is also nearly parameter free and resolution independent.source