Logical Layout Analysis Applied to Historical Newspapers (2021)

Abstract: In recent years, libraries and archives led important digitisation campaigns that opened the access to vast collections of historical documents. While such documents are often available as XML ALTO documents, they lack information about their logical structure. In this paper, we address the problem of logical layout analysis applied to historical documents. We propose a method which is based on the study of a dataset in order to identify rules that assign logical labels to both block and lines of text from XML ALTO documents. Our dataset contains newspapers in French, published in the first half of the 20th century. The evaluation shows that our methodology performs well for the identification of first lines of paragraphs and text lines, with F1 above 0.9. The identification of titles obtains an F1 of 0.64. This method can be applied to preprocess XML ALTO documents in preparation for downstream tasks, and also to annotate large-scale datasets to train machine learning and deep learning algorithms.

## introduction one important challenge in digital humanities is the efficient exploitation and processing of scanned textual documents (archives, documentary funds, ...). for example, historical documents such as newspaper archives are prime resources for historians @xcite . thanks to the important digitisation campaigns led by libraries and archives, vast collections of historical documents have been made easily accessible. however, the majority of these documents are available only as scanned images (e.g. in pdf format) which makes them difficult to explore in a text processing perspective. extracting the text content from such documents requires at least the following three steps: optical character recognition (ocr), physical layout analysis (pla) and logical layout analysis (lla). physical layout analysis (pla), which is also sometimes called document layout analysis, consists in identifying physical regions of the document, with their text content and boundaries. such regions can correspond to sections and lines of text, but also to figures, tables, etc. pla also defines the reading order of the document, which corresponds to the linear order in which the different regions appear. this is particularly important for documents that have multi-column layouts. one commonly used output format of pla is the xml alto format foot_0 . logical layout analysis (lla), sometimes called logical structure derivation and structure understanding, consists in identifying the document structure elements and their categories i.e. title, header, paragraph, table, etc. such logical elements can integrate one or more regions in the document that have been identified by pla. physical and logical layout analyses are necessary steps in the processing of documents for a large number of applications, including information retrieval, information extraction, table of content extraction, text syntheses, and more broadly document understanding. in this article we focus on the problem of logical layout analysis (lla). we describe a methodology for logical layout analysis, where logical labels are assigned to physical layout entities. the input of our processing pipeline is the physical layout analysis of documents in the xml alto format. the rest of the article is organised as follows: the following section presents the related work on logical layout analysis. section 3 present our train and test datasets. section 4 presents the methodology that we propose and section 5 proposes an evaluation of the implemented processing pipeline. finally, we propose a conclusion and a discussion. ## related works an important body of research around physical layout analysis of printed documents has been produced in the end of the xx th century. several algorithms have been proposed such as the x-y cut algorithm @xcite , the docstrum algorithm @xcite or the voronoi diagram based algorithm @xcite . furthermore, the processing of handwritten documents requires specific techniques, such as the "droplet" technique to identify text line by @xcite , or neural networks as in @xcite , where each pixel is labelled as text or not. existing logical layout analysis systems make use of various methods that go from heuristic systems to more recent architectures using neural networks. some heuristic systems use grammars such as stochastic or attributed grammars, where the document is represented as a string of symbols, e.g. @xcite . in their work, the grammar describes multiple production rules, each associated with a logical label. the string of symbols is then parsed by the grammar in order to extract logical labels. other systems, such as la-pdftext @xcite or delos @xcite , use rules that state the condition a physical block must meet to be given a logical label. for instance, delos system uses first-order predicates in order to infer the logical category of a physical block. while heuristic systems provide good results, they are often dedicated to specific layouts, and need to be adapted to work on other layouts. to tackle this problem, @xcite created a system for logical layout analysis on scientific articles in pdf format that combines heuristic rules with unsupervised-learning models such as k-means or hierarchical agglomerative clustering (hac). this system is made up of several detectors, each learning geometrical and textual features from the document in order to identify a specific logical label. some rules using text occurrences are also used to help the model, such as finding the keywords "table " or "fig. " to identify table or figure blocks. more recent works use neural networks for logical layout analysis. as noted by @xcite , cnn or lstm architectures work better than classical neural networks because of the sequential nature of the documents. this task also benefits from the use of word-embeddings such as fasttext, flair or glove which give a better encoding of textual data than simple one-hot encodings, as in @xcite . neural network systems can be trained on big datasets such as the publaynet dataset @xcite or the medical articles record groundtruth (marg) for physical and logical layout analysis purposes. considering the task of processing historical documents, several small datasets exist such as the diva-hisdb dataset @xcite which contains 150 annotated pages of three different medieval manuscripts or the european newspapers project dataset @xcite which contains 528 documents. other datasets in non-european languages exist, such as the phibd dataset (hossein ziaie nafchi and cheriet, 2012), which contains images of 15 persian historical and old manuscript, and the hjdataset by @xcite , which contains 2271 japanese newspapers published in 1953, which was generated in a semiautomatic way. all of these datasets are too small to be used for machine learning or neural network approaches. @xcite deal with the task of article segmentation by a conditional random field (crf) model with heuristic rules to perform logical analysis. first the crf model labels pixel as titles, text lines, or horizontal and vertical separators, then heuristics rules describing usual article layouts are applied to that classification. in both cases, bad results were caused by the quality of the scan or the quality of the ocr output. on the other hand, @xcite deal with article segmentation by looking at the similarity between segments of texts. these segments are computed either by using the jaccard coefficient and their word distribution or by computing the cosine similarity between wordembeddings. the similarity between blocks is then computed using the texttiling algorithm @xcite most common approaches to lla are not suited for historical documents because the document layout changes over time. for example, the layout and structure of an advertisement in the same newspaper can display important changes over several years. logical layout analysis systems applied to historical documents must then account for the diachronic aspect of their layouts and adapt to the changes. @xcite propose a system that goes beyond usual logical labels by labelling physical block as either serial, weather forecast, death notice and stock exchange table . to do so, their system combines visual and textual features using the word-embedding representation of each word and its coordinates on the page. their results show that combining textual and visual features provide better results in most cases than using just one of them. textual features are also more efficient to deal with the diachronic aspect of documents because they are more stable over time than visual features. ## dataset we have processed a dataset of press and magazine documents published in the first half of the 20th century from the "fond régional: franche comté" collection, available from the digital archive of bibliothèque nationale de france 2 . figure 1 shows an example of the first page of a newspaper with more than 2 columns. it contains the header of the first page and several articles that contain titles and text content. from this collection, we selected documents that had an ocr quality measure greater than 90%. this dataset was then split into a train and a test dataset. as shown in the french language used in these documents is not very different from modern french. however, we notice some variations in the written styles between the three topics. the written style in the catholic document is formal and literary and uses many religious metaphors. on the other hand, the written style in the news document is mostly standard, although sometimes formal. sentences are shorter and use simpler tenses than the catholic documents. this simplification of the writing style is even more prominent in resistance documents. the difference in the writing style between documents can first be explained by their domain: religious text should be more literary than newspapers or resistance periodicals. this difference can also be explained by the size of the documents. catholic documents are the longest in the corpus, with more than 10 pages on average. as such, their text can be more elaborate. on the other hand, news and resistance documents are respectively four and two pages long on average. their text is factual and concise in order to convey a lot of information in the limited space they have. all the documents are stored in the xml alto format, which contains descriptions of their physical layout and the text content obtained from ocr. as such, the files already provide the physical layout analysis and the reading order of the documents. the xml alto format provides the text convpos the vertical position of the text on the page. the higher the value, the lower the word is on the page hpos the horizontal position of the text on the page. the higher the value, the further on the right the text is on the page language the language of the text (only for textblock tags). among the attributes listed above, some textblock tags also have a type attribute. this attribute is useful as it contains the logical labels of the lines in the block. it appears most often for tables or advertisements. however, textblock with a type attribute are rare in our dataset. as shown in ## methodology our algorithm aims to attribute logical layout labels to both textblock and textline tags in documents. in the following subsections, we present the tagset that is used, then we explain the general processing pipeline of the algorithm. finally, we present in detail the features that are used by the algorithm and the sets of rules. the diagram in figure 2 shows the processing pipeline as described in this section. we defined sets of rules for the annotation of textblock and textline tags. they are applied to documents regardless of the layout category they belong to. these rules were designed using heuristics based on observations that we made in the train dataset. for instance, we observed that the biggest titles in the documents start with a capital letter and are surrounded by important spaces. then, we translated these patterns into rules that we could use. this required us to extract features from the xml alto document, and to compute other features that are not available directly, such as the space between lines or the case of the first letter of a line. ## evaluation to evaluate our method and the proposed annotation rules we have run the algorithm through the test dataset. textblock annotation is an intermediary step in the algorithm. textblock annotation rules perform best on documents from the 2c layout category. title classification for textblocks performs with f1 score of 0.61 on average and 0.94 on documents from the 2c category. header classification for textblocks provides a good precision score (0.726) but with a low recall (0.298). similarly to textblock annotation rules, textline annotation rules perform best on docu-ments from the 2c category. title identification performs worse on 1c documents, and obtains overall f1 score of 0.639 for all layouts. firstline identification performs fairly well with an f1 score above 0.9. header identification obtains a good precision score (0.803) but with a recall of 0.348. this means that header identification rules are insufficient and need to be completed to capture the various types of headers. a first type of error comes from errors in the block classification step. as any line in a title or header block inherits that annotation, the precision of textblock annotation is an important factor for the overall performance of the algorithm. a second type of error is the confusion between titles and first lines. most titles mislabelled as firstline are short subsection titles. as such, they are similar to other text lines in terms of typography, and are hard to detect with the features we use. this confusion happens mainly in documents from the 2c and 3c+ categories. other mislabelled titles are one-line paragraphs such as greetings or signatures, or the beginning of a text section. such lines have properties similar to titles, being surrounded by important spaces and being either center or rightaligned. extracting features about the font style of the line (bold, italics) and its alignment (left, center, right-aligned) could help solve this confusion. ## conclusion and discussion in this article, we have presented a rule-based system for the logical layout analysis of xml alto documents. our system starts by extracting features from the document, then uses these features to add logical labels to textblock and textline tags. we have described the construction and the evaluation of the proposed annotation while recent methods in nlp use extensively machine learning and deep learning architectures, such approaches require large annotated datasets. to the best of our knowledge, no such datasets exist for the logical layout analysis of historical newspapers in french. for this reason, the algorithm that we propose in this paper is manually designed and rule-based. its objective is, above all, to be able to produce annotated datasets that are large enough to envisage machine learning or deep learning approaches. the comparison between the performance of these rules and the results of recent deep learning architectures will be the object of our future work. we devised the rules to process documents re-gardless of their era. as stated earlier, the layout in historical documents evolves rapidly, especially in newspapers. in order to create sets of rules dedicated to the different publication periods, we plan in future works to apply rule learning algorithms to generalise the creation of rules.