Document Analysis and Layout Using Sequential Pattern Mining Techniques

Long read

This article describes a method to mine and discover how documents are organized in terms of layout and information using Sequential Pattern Mining techniques. This step is key in enabling Information Extraction, a critical task for archival documents since the vast majority are not reports or narratives, but tables, lists and registry books. This work is carried out within the EU project READ.

Document Understanding

Defined as ‘the field that is concerned with logical and semantic analysis of documents to extract human understandable information and codify it into machine-readable form.” [1] Document Understanding means that once scanned as images, archival documents need to be processed to automatically extract text, and eventually information. After the lines of text in the page image have been identified (Layout Analysis) and Handwritten Text Recognition performed, we take the results as the input to perform Document Understanding.

To illustrate what’s involved, let’s take a look at the page below provided by one of our partners, the Passau Diocesan Archives. It’s a page from a wedding register that dates back to the 18^th century. Readers, such as family genealogists, are interested in information (data) such as who got married, and where and when the wedding took place. While this page provides such information, several processing steps are required to extract it.  Suppose we have at our disposal a Layout Analysis as well as a Handwritten Text Recognition tool to generate the set of lines and their transcriptions. The Document Understanding task consists in finding the semantic relations among the lines in order to structure them into meaningful information:  in this case that means grouping the lines of each wedding together, to join the right groom with the right bride on the right day.

Two Assumptions

To achieve our Document Understanding task, we rely on two strong assumptions: First, that documents (their layout and content) are not at all randomly organized and very often follow some kind of template. This helps a lot in ‘understanding’ them. Secondly, these templates can be discovered by mining documents and searching for regularities within them.

Our notion of ‘document template’ is that a document is an artificial object designed by humans for humans, and often follows some (common) design practices.  One simple example of these design practices or templates is ruling: The process by which a frame and/or horizontal lines are produced in order to guide the hand in writing [2].

The ruling template is strongly layout oriented, and answers the question on how to organize the page (see also [3]). Other interesting templates concern the organization of the content and the text in correlation with the (geometrical) layout. A basic novel may be structured as only a set of paragraphs, but when the content is data-oriented, there is a need for templates that interweave content and layout. In our example, the wedding register is organized as a list of weddings, starting with the wedding day (centered at the top), and the information structured with keywords (‘sponsus’, ‘sponsa’, ‘testes’). The marginalia notes index the first names of the groom and bride.  This makes it easy for readers to browse and search for this data.

Mining a document to find regularities

In template that combine layout and content the main issue is how to identify what the template is. The idea we had to do this is to apply some well-known methods used in Sequential Pattern Mining from the Data Mining field.

If we consider a document as a database, instead of mining a database proper, we mine a specific document to find out the sequential patterns that display interesting regularities. These patterns (which will eventually constitute the templates) correspond to document objects. This approach relies on the underlying assumption of following some design rules. Being able to uncover these rules and layout patterns, allows the machine to better understand how the document is organized and therefore better extract the information it contains.

Before giving an example of how this works here’s a very brief explanation of Sequential Pattern Mining which ‘discovers frequent sub-sequences as patterns in a sequence database. A sequence database stores a number of records, where all records are sequences of ordered events’ […] [4]

Suppose you have a database which the following 4 sequences (S1…S4):

Sequence ID	SEQUENCES
S1	<{a,b},{c},{f,g},{g},{e}>
S2	<{a,d},{c},{b},{a,b,e,f}>
S3	<{a},{b},{f},{e}>
S4	<{b},{f,g}>

Each sequence is composed of a list of ordered itemsets. Each itemset is composed of several basic items which characterize the itemset (e.g. a,b,c,… in our example). A sequence pattern mining algorithm will automatically extract the frequent patterns from these sequences.

Suppose you want all patterns with a frequency (called support in this field) greater than 2, the algorithm will generate the following list of patterns. The most frequent pattern <{a},{f}> is extracted from sequences S1, S2 and S3, hence a support of 3.

ID	Pattern	Support
P1	<{a},{f}>	3
P2	<{a},{c},{f}>	2
P3	<{b},{f,g}>	2
P4	<{g},{e}>	2
P5	<{c},{f}>	2

 

So far so good. But the main technical issue for these pattern mining techniques is to deal with the combinatorial number of potential patterns a large list of itemsets can generate. Mining hundreds or thousands of sequences has to be fast, and the algorithms in the literature mostly focus on optimizing speed.

So ,what does all this have to do with Document Understanding? Well you can view a document as a sequence of pages, a column as a sequence of lines and so on. More logical elements can also be involved e.g. a section is a sequence of paragraphs, a paragraph is a sequence of sentences, etc.

Using sequential pattern mining techniques allows us to automatically create patterns corresponding to various document structures. Our method is a modification of the one described by Pei et al in [5], but our purpose here is not to explain the details, but rather to show how it is relevance to our problem.

So, let’s apply a similar algorithm to a ‘database’ composed of a set of lines from one page taking the same example as earlier of the wedding registry. Using Sequential Pattern Mining our objective is to assign patterns to the page represented as a sequence of lines, and identify ifthere’s any pattern that corresponds to a useful line organization.

Rectangles

Unlike many approaches in Layout Analysis (LA), we don’t take the scanned image as input, but the outcome of the Layout Analysis. This can be roughly described as a main rectangle (the page) containing a set of regions. These regions can correspond to lines and blocks of lines. The line region can be represented by polylines or in a first approximation, by the rectangle encompassing the line. You can see how this works in the images below with the original page on the left (1a) alongside the detected lines represented by rectangles on the right (1b). You can see the line detection is far from perfect! The LA results depend on the image input which vary from being precise to very noisy. We assume that the LA input is noisy, but good enough to allow us to detect patterns.

To make the parallel with the database sequences, lines play the role of the itemsets. We need to find the basic items which characterize the sequence of lines. These characteristics are geometrical (see Figure 2) and reflect the position of the line in its column: left-x (x1), centered-x (xc), right-x (x2).

The current page can now correspond to our ‘database’ where each line is a database entry. To make the explanation simpler and smaller, we assume the main column has been identified, and we ignore the marginalia. The sequence we mine is therefore the following (using a simplified version of Figure 1(b)!):

Line ID	Features
12	x1=271.0, xc=323.0, x2=379.0
45	x1=129.0, xc=293.0, x2=457.0
25	x1=129.0, xc=293.0, x2=457.0
37	x1=129.0, xc=250.0, x2=313.0
57	x1=129.0, xc=293.0, x2=457.0
134	x1=129.0, xc=293.0, x2=457.0
129	x1=129.0, xc=229.0, x2=313.0
122	x1=129.0, xc=293.0, x2=457.0
120	x1=271.0, xc=293.0, x2=358.0
112	x1=129.0, xc=293.0, x2=457.0
105	x1=129.0, xc=293.0,x2=457.0
103	x1=129.0, xc=149.0, x2=168.0
164	x1=249.0, xc=309.0, x2=358.0
169	x1=129.0, xc=293.0, x2=457.0
177	x1=129.0, xc=293.0, x2=457.0
185.1	x1=129.0, xc=250.0, x2=358.0
190	x1=129.0, xc=293.0, x2=429.0
196	x1=129.0, xc=293.0, x2=457.0
204	x1=129.0, xc=250.0, x2=358.0
209	x1=129.0, xc=293.0, x2=457.0
217	x1=129.0, xc=250.0, x2=429.0
67	x1=271.0, xc=293.0, x2=313.0
263	x1=129.0, xc=293.0, x2=429.0
270	x1=129.0, xc=293.0, x2=457.0
277	x1=129.0, xc=250.0, x2=379.0
92	x1=208.0, xc=283.0, x2=358.0
255.1	x1=129.0, xc=293.0, x2=457.0
255.2	x1=129.0, xc=293.0, x2=457.0

So now we have our data. The Data Mining step will then mine this data to find patterns. We use a modification of [5] to detect repetitive patterns: a pattern which occurs in a contiguous way, such as <a,a,a>. These patterns are denoted with the Kleene Star (+).Applying the sequential pattern mining algorithm to this ‘database’ generates the following patterns of length one:

Pattern	Support
[x1=129]+	24
[xc=293]+	22
[x2=456]+	15

This basis analysis groups lines according to their alignment (left-aligned, centered or right-aligned).  Considering longer patterns, some techniques allow us to generate more sophisticated patterns like the following ones:

Pattern	Support
xc=293.0, [x1=129.0]+	29
[xc=293.0 ]+,x1=129.0	29
x2=457.0, [x1=129.0]+	17

The first pattern in this table can be read as: a centered element (xc=293) followed by a sequence of left-aligned lines ([x1=129.0]+). This result is more interesting because it’s a visual representation of the grouping of lines using this pattern: a sequence of centered (green) and left-aligned (blue) sets of lines as shown in Figure 3.

Interestingly the second most frequent pattern gives a different segmentation: the same lines but organized in a different way. Both patterns cover the same elements (all the elements of the page), but differently. So how do you decide which pattern is relevant? Generating patterns is not so difficult but you need context and external knowledge to selecting the most relevant ones.

At this stage, it’s difficult to select one pattern for our example. But we can go further in the Pattern Mining step by integrating a new piece of information which is content. Suppose we apply a Handwritten Text Recognition engine to the page. The Pattern Mining process can then integrate the text as the source of new features. By combining layout and content, the longest pattern generated is then the following:

firstW=Die, [x1=129]+, firstW=testes, [x1=129]+

This formula is read as: a line starting with the word ‘Die’, followed by a sequence of lines, left-aligned, then a line starting with the word ‘Testes’, followed by a sequence of left-aligned lines. This is a pattern which corresponds to the structure of the wedding record of the page! Other deeper mining can be applied to identify more detailed patterns of the wedding e.g. (sponsus:XXX, sponsa XXX), and so on.

Information Extraction

Being able to group together all the lines of a single wedding is very important for the Information Extraction task. Thanks to the Document Understanding step all entities that are part of the wedding (bride, groom, date, witnesses…) are related together building a single record.

This tiny example shows how Data Mining can be applied to ‘understand’ the line organization of a page. We use similar methods to find other patterns such as page body and margins, multi-columns or the page header and footer. The process is always the same: identify a sequence of elements, characterize the elements with a set of characteristics, and apply the Sequential Pattern mining algorithm.

A key advantage we’ve found with this method is that it only requires data (documents) and it’s self-adaptive. According to the document, different patterns can be generated. If you look at the  full document, you’ll see that the pattern found for our page occurs from page 1 to page 5, then a ‘simpler’ pattern is used, where the witnesses part is integrated in the left-aligned part, but still identifiable with the keyword ‘testes’ at the beginning of the line. Similarly, the simple page layout (mirrored pages with marginalia) changes at page 112, to be replaced by a tabular layout.

In the next post I’ll explain how this same technique can be applied to mine the main page layout elements like the margins and page body!

—————————————————————————-

This work is carried out within the European Project READ within the H2020 e-infrastructure programme (grant agreement No 674943). READ aims at implementing a Virtual Research Environment where archivists, humanities scholars, computer scientists and volunteers collaborate with the ultimate common goal of boosting research and the use of recent technology for the automated recognition, transcription, and enrichment of handwritten archival documents. The project is coordinated by Dr. Günter Mühlberger (University of Innsbruck).

Further reading about Data Mining

http://simpledatamining.blogspot.fr/2015/03/generalized-sequential-pattern-gsp.html

http://data-mining.philippe-fournier-viger.com/introduction-frequent-pattern-mining/

http://data-mining.philippe-fournier-viger.com/an-introduction-to-the-discovery-of-periodic-patterns-in-data/

http://data-mining.philippe-fournier-viger.com/introduction-to-sequential-rule-mining/

References

[1]    Dengel, A., Shafait F., Analysis of the Logical Layout of Documents, DOI: 10.1007/978-0-85729-859-1_6

[2]     Brown, M.  P., 1994. Understanding Illuminated Manuscripts: a guide to technical terms, Getty publication.

[3]     Shailor, B. A. The Medieval Book: Illustrated from the Beinecke Rare Book and Manuscript Library,

[4]     Nizar R. Mabroukeh and C. I. EZeife, A Taxonomy of Sequential Pattern Mining Algorithms, ACM Computing Surveys, Vol. 43, No. 1, Article 3, Novembre 2010, http://dl.acm.org/citation.cfm?id=1824798, 10.1145/1824795.1824798]

[5]     Pei, J. et al, PrefixSpan: Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth,DOI: 10.1109/ICDE.2001.914830

This project has received funding from the European Union’s Horizon 2020 research and innovation programme under grant agreement No 674943.

These preprocessing tasks are performed by our READ partners, namely the Computational Intelligence Laboratory, Institute of Informatics and Telecommunications, National Center for Scientific Research “Demokritos” in Athens and the Computer Vision Lab group of the Technical University Vienna for Layout Analysis and the Pattern Recognition and Human Language Technology group of the Technical University Valencia and the Computational Intelligence Technology Lab of the University Rostock for Handwritten Text Recognition.

Related information and publications:

Transkribus Python Toolkit,Hervé Dejean and Jean-Luc Meunier, ICDAR-OST, Kyoto, Japan, 10th – 12th November, 2017

PyStruct Extension for Typed CRF Graphs, Jean-Luc Meunier, ICDAR-OST, Kyoto, Japan, 10th – 12th November, 2017. Describes new library publicly available on GitHub under the Simplified BSD License.

Using Ancestral Layout Models for Document Digitization, Hervé Dejean,  DaTECH conference on Digital Access to Textual Cultural Heritage, Madrid, Spain, 19^th – 20^th May, 2014