AIDAS: Incremental Logical Structure Discovery in PDF Documents

Anjo Anjewierden
Social Science Informatics, University of Amsterdam
Roetersstraat 15, 1018 WB Amsterdam, The Netherlands
anjo@[Link]

Abstract Discovering the logical document structure.

The fragments that AIDAS needs to store correspond
We describe the approach AIDAS uses to extract the logi- to the logical document structure (sections, tables, im-
cal document structure from PDF documents. The approach ages, items, etc.). During this stage the layout structure
is based on the idea that the layout structure contains cues is incrementally analysed in order to discover the logi-
about the logical structure and that the logical structure can cal structure (see Sections 3–4).
be discovered incrementally.
Indexing and fragmenting the logical structure.
The logical structure produced by the previous stage
is annotated using a domain ontology and reasoning
1. Introduction about the logical structure [4]. During this stage AIDAS
looks at the content of the logical structure, for exam-
AIDAS is part of a research project in which the aim is to ple comparing the title of a section to the list of con-
turn technical manuals into a database of indexed training cepts in the ontology. If a match between a title and
material. The role AIDAS plays in this project is to take a concept occurs, the section is indexed as a fragment
a PDF file, extract the logical structure and assign indexes with the name of the concept as the topic. This stage is
to each element in this logical structure. The indexes can not further discussed in this paper.
either be about the content of the element (e.g. “this section
is about the rear part of a car”, “this is a schematic drawing Storing the document in a multi-media database.
of the control unit”) or about how the element can be used This takes the annotated fragments and converts them
in instruction (e.g. “this section provides a brief overview to a database. Text fragments are stored as ASCII and
of the components of a car”). An instructor can retrieve graphical fragments are stored as SVG [8].
appropriate training material by querying the database using
the indexes.
The advantages of an automated approach to indexing
2. PDF vs. scanned images
training material and making it available electronically may
be apparent. Whereas until recently the industrial partners PDF represents a document as a set of instructions.
in the project literally used scissors and glue to produce the When these instructions are processed by the PDF image
material, they can now use the indexed database and cut- model a bitmap is generated which can be rendered on a
and-paste to presentation programs. graphics device. The instructions in PDF fall into four cat-
In order for AIDAS to be able to do its work we distin- egories: (1) control instructions which work on the image
guish the following stages: model and produce no output; (2) text instructions render
glyphs; (3) graphics instructions render lines, curves and
Interpreting PDF. rectangles etc.; and (4) image instructions render bitmapped
The starting point for AIDAS is a document in PDF [1]. images.
PDF (Portable Document Format) is a page descrip- Many document analysis systems take a scanned image
tion language that is powerful in terms of the rendering as the source and extract text, graphics and images from
capabilities it provides and widely used for document it. Such systems could also deal with PDF by including a
exchange. Section 2 describes how AIDAS extracts the pre-processing step that renders PDF in a bitmap. We have
layout structure from PDF. chosen for a design in which the stream of PDF instructions

1
is converted to a set of text, graphics and image objects. using top-down techniques (grammars).
This conversion is implemented on top of xpdf [5].
The layout structure used by AIDAS consists of the set 4. Implementation
of objects generated by the conversion. There are about ten
different classes of layout objects (text, line, rectangle, im-
age, curve, etc.). And each of these classes has about ten The first step performed by AIDAS is to identify the over-
features (position, font face, font size, color, line width etc.). all layout of a document. This step identifies the columns,
A complication of PDF that does not occur with scanned headers and footers, and the dominant font. All of these are
images is that there are an infinite number of different PDF determined by statistical analysis and can be overridden by
documents that render precisely the same image. For exam- the user. This process is easier in PDF compared to scanned
ple, a word can be a single text object or there can be sep- images.
arate text objects for each character in the word. However, Thereafter AIDAS breaks up each page in segments.
the layout structure generated from PDF is more reliable Drawings are recognised by many graphical elements ver-
than extracting the layout structure from scanned images. sus few text elements and tables are recognised by a lot of
There are complications, however, for example the issue of text classified as floating. All remaining segments are text
visibility. A PDF document could contain an instruction to segments.
render some text followed by an instruction to render a filled
rectangle on top of it. 4.1. Classifying individual layout objects

The next step is to look at individual layout objects gen-

3. Logical structure discovery
erated by the PDF interpreter. During this step AIDAS clas-
sifies each layout object on several dimensions: geometry,
The logical structure (sections, item lists, tables, etc.) markup and (textual) content.
is not explicitly available in the layout structure and needs For example, given the following layout object:
to be discovered. Various approaches to logical structure
discovery have been suggested. If the document style (e.g. <text>
font face and size of section titles, line spacing, number of <layout x=25 y=200 w=180 h=14
columns) is available then the use of top-down grammars face="Times-Bold" size=12/>
that incorporate the document style is possible, but even 1.1 Introduction
then extensive error recovery is necessary to cater for id- </text>
iosyncrasies [3]. An alternative approach is to first discover
a hierarchy of layout objects (glyph, word, line, text block, the classification results in:
column) and then map this hierarchy on the logical docu-
ment structure hierarchy [9]. This approach will work well <text>
if the two hierarchies can be easily mapped on each other. <layout x=25 y=200 w=20 h=14
The approach in AIDAS is based on the idea that layout face="Times-Bold" size=12/>
objects represent only their layout features explicitly, but <geometry alignment=left/>
that these features contain cues about the role in the logical <markup size=larger emphasis=bold/>
structure [6], [7]. For example, a text object in a large bold <function sectionnum="1.1"/>
font (the form) contains the cue that it could be a section 1.1
title (the function), and a text object containing the literal * </text>
(form) could be a bullet (function). The distinction between
form and function is also seen at the logical structure. For <text>
example, a paragraph (form) can be the body of a bullet or <layout x=50 y=200 w=155 h=14
an item (function) or it can, along with other paragraphs, be face="Times-Bold" size=12/>
the body of a section. An extreme case is that the paragraph <geometry indentation=25/>
may be the title of a section in the case of a title spanning <markup size=larger emphasis=bold/>
multiple lines. Introduction
AIDAS uses this idea by assigning a set of possible func- </text>
tions to each layout object and incrementally chunking them
to more complex objects. This process is performed incre- The geometry element has been abstracted from the
mentally until the logical structure is produced. Determin- column boundaries, the markup element from the domi-
ing the possible functions of a layout object can be done nant font and the function element has been determined by
in a bottom-up fashion, whereas the function is determined matching the text against the patterns for section numbers.
This form abstraction can proceed without regard of the sur- <markup size=larger ... />
rounding text because no information is lost. Should it later <function sectionnum="1.1"/>
be discovered that the “1.1” object is not a section number 1.1
then the abstractions are ignored and, perhaps, the two text </text>
objects are concatenated again (for example as part of the </sectionnumber>
phrase “see also Section 1.1 Introduction”). <sectionname>
Other examples of abstractions are bullet characters (“*”, <text>
“-”, etc.), enumeration indicators (“(a)”, “1)”, etc.) and, <layout x=50 y=200 w=155 h=14 .../>
specifically for technical manuals, references to figures <geometry indentation=25/>
(“General Theory of Operation (Fig. 14-15A)”. <markup size=larger .../>
Introduction
4.2. Shallow grammars to detect logical elements </text>
</sectionname>
The logical structure itself is discovered by taking the </sectiontitle>
set of layout objects, sorting them on y/x position and then
The incremental nature of the process can be illustrated
running a set of shallow grammars on them. Each of these
further by considering how the next level in the logical
grammars detects a specific element of the logical structure
structure, sections, is discovered:
and leaves the objects that do not match untouched. This ar-
chitecture has several pleasant characteristics: (a) the gram- section(Section) -->
mars are shallow and complexity is roughly linear; (b) new section_title(Title),
grammars that discover other logical structure elements can section_body(Body),
easily be added; and (c) no error recovery is necessary as Section is
the grammars ignore unrecognised input. section(Title, sectionbody(Body)).
A simplified version of the grammar for detecting section
titles is given below: section_title(Title) -->
Title is next_node,
sectiontitle(SectionTitle) --> element(Title, sectiontitle).
section_number(Num),
section_name(Name), section_body(Body) -->
SectionTitle is /* Collect everything until a
sectiontitle(sectionnumber(Num), sectiontitle element is seen. */
sectionname(Name)).
In the current implementation grammars for the follow-
sectionnumber(Num) --> ing logical elements are used: section titles, sections, bul-
Num is next_node, lets, bullet lists, items, item lists, headings, paragraphs, ta-
match(Num, function, sectionnum=N), bles and figures.
match(Num, geometry, alignment=left), The final step is to remove all abstractions from the ob-
match(Num, markup, emphasis=bold), jects and output the logical structure itself. For the above
match(Num, markup, size=larger). example this results in:

sectionname(Name) --> <section level=2 id="1.1">

Name is next_node, <sectiontitle>Introduction</sectiontitle>
match(Name, geometry, indentation=N), <sectionbody> ... </sectionbody>
match(Name, markup, emphasis=bold), </section>
match(Name, markup, size=larger). This logical structure is then processed by the indexing
and fragmentation module of AIDAS [2].
A match results in the replacement of layout objects by
a structural object that represents a section title:
5. Experimental results
<sectiontitle>
<sectionnumber> At the time of writing AIDAS is being used by the in-
<text> dustrial partners to fragment technical manuals in three do-
<layout x=25 y=200 w=20 h=14 .../> mains: car repair; military equipment; and electronic con-
<geometry alignment=left/> trol systems for traffic lights.
 The car repair manuals have a very specific logical struc- on Artificial Intelligence (BNAIC), pages 23–30, Amsterdam,
ture. For each topic (e.g. body work) there is a separate October 2001.
section with short descriptions and lots of figures of the car [3] T. Hu and R. Ingold. A mixed approach toward an efficient
and how to use tools for repair. A domain specific shallow logical structure recognition from document images. Elec-
tronic Publishing, 6(4), December 1993.
grammar has been added to recognise this structure and it
[4] S. Kabel, B. Wielinga, and R. de Hoog. Ontologies for index-
performs very well according to the users. ing technical manuals for instruction. In Workshop on On-
The manuals for the military equipment (radar-based in- tologies for Intelligent Educational Systems, Le Mans, July
terception) consist of a mix of theory and technical draw- 1999.
ings. The theoretical material is in four columns (A3 pages) [5] D. Noonburg. xpdf: A C++ library for accessing PDF.
and the drawings are in separate books with captions. One [Link]/xpdf.
of the problems here was to create a link between the books [6] K. Summers. Toward a taxonomy of logical document struc-
containing the theoretical sections and the books containing tures. In Electronic Publishing and the Information Super-
the technical drawings. We have not received a formal eval- highway: Proceedings of the Dartmouth Institute for Ad-
vanced Graduate Studies (DAGS), pages 124–133, 1995.
uation for this material, but experiments on parts show that
[7] K. Summers. Automatic discovery of logical document struc-
extracting the logical structure from the text is more than ture. PhD thesis, Cornell University, August 1998.
acceptable. [8] W3C. SVG (Scalable Vector Graphics). [Link].
One of the virtues of the incremental approach used in [9] Y. Wang, I. Phillips, and R. Haralick. From image to
AIDAS is that it is “robust” with respect to unexpected input. SGML/XML representation: one method. In International
Although it will not recognise the unexpected input (and workshop on Document Layout Interpretation and its Appli-
therefore leave it as layout objects), domain specific shal- cations (DLIA), Bangalore, India, September 1999.
low grammars can be added to recognise additional logical
structures if necessary. This is very important for technical
manuals, as there is no such thing as “a logical document
structure” for technical manuals as is illustrated by the mil-
itary and car domains. Technical manuals take into account
the skills of the readers: in the military domain theory is
supplemented by figures, whereas in the car repair domain
the emphasis is on manual skills which is mainly supported
by figures.
The figure on the last page shows a screendump of the
tool after analysing a page from the military domain. The
rectangles represent segments. To the left of each recog-
nised logical structure element is a the name of the element
(e.g. sectiontitle, item, paragraph, heading). Colour is used
to show to the user what part of the text is recognised.

6. Acknowledgements

The work presented in this paper has been supported by

the European Commission as part of the IMAT (Integrating
Materials and Training) project. We gratefully acknowledge
comments on previous versions of this paper by Jan Wiele-
maker and Robert de Hoog. We also would like to thank the
three anonymous reviewers whose comments we have tried
to take into account.

References

[1] Adobe Systems Incorporated. PDF Reference version 1.3.

Addison Wesley, Boston, second edition, July 2000.
[2] A. Anjewierden and S. Kabel. Automatic indexing of doc-
uments with ontologies. In 13th Belgian/Dutch Conference
Figure 1. AIDAS analysing a technical manual