An Algorithm for Finding Maximal Whitespace Rectangles at Arbitrary Orientations for Document Layout Analysis

Thomas Breuel

In: International Conference for Document Analysis and Recognition (ICDAR). International Conference on Document Analysis and Recognition (ICDAR) Edinburgh IEEE Computer Society 8/2003.


The analysis of the background structure (whitespace) of page images has become an important technique for phys- ical document layout analysis. Globally maximal whites- pace rectangles have been previously demonstrated to con- stitute a concise representation of the major layout fea- tures of documents. However, previous methods for computing maximal whitespace rectangles were limited to axis- aligned rectangles. This paper presents an algorithm that finds globally maximal whitespace rectangles on page images at arbitrary orientations. The new algorithm eliminates the need for page rotation correction prior to back- ground analysis and can be applied to considerably more complex page layouts than previously possible. The algo- rithm is resolution independent and takes as input a list of foreground shapes (e.g., character or word bounding boxes or polygons) and a set of parameter ranges; it outputs the N largest non-overlapping maximal whitespace rectangles whose parameters (location, width, height, orientation) fall within the required parameter ranges. Examples of appli- cations of the method to severely skewed documents, as well as the UW3 database, are presented.

2003-breuel-icdar.pdf (pdf, 993 KB )

Deutsches Forschungszentrum für Künstliche Intelligenz
German Research Center for Artificial Intelligence