Sébastien Eskenazi
email: sebastien.eskenazi@univ-lr.fr

Petra Gomez-Krämer

Jean-Marc Ogier
email: jean-marc.ogier@univ-lr.fr

A comprehensive survey of mostly textual document segmentation algorithms since 2008

Keywords: Document, Segmentation, Survey, Evaluation, Trends, Typology

In document image analysis, segmentation is the task that identifies the regions of a document. The increasing number of applications of document analysis requires a good knowledge of the available technologies. This survey highlights the variety of the approaches that have been proposed for document image segmentation since 2008. It provides a clear typology of documents and of document image segmentation algorithms. We also discuss the technical limitations of these algorithms, the way they are evaluated and the general trends of the community.

Introduction

Industrial document digitization, document archiving with destruction of the original copy and security technologies based on document processing create an increasing need for reliable document processing algorithms. A thorough list of the available algorithms would be of great use to choose them correctly. A typical paper document content extraction process is shown in Figure 1. Document segmentation aims at dividing the document image into meaningful parts. These parts can be glyphs, words, text lines, paragraphs, regions (usually with one type of content such as text or graphic).

These parts are usually used for further content extraction such as text recognition, to determine the reading order, or to classify the document.

10

In order to split the document image properly we may need to understand its content and vice versa. This paradigm is related to the associationist and Gestalt theories of vision [START_REF] Treisman | A feature-integration theory of attention[END_REF]. This is why document segmentation algorithms can include and work in symbiosis with a classification algorithm that will identify the content of the document. One of the first document image segmentation algorithms appeared in 1982 with the Run-Length Smoothing Algorithm (RLSA) [START_REF] Wong | Document analysis system[END_REF]. It was followed in 1992 by the X-Y cut algorithm [START_REF] Nagy | A prototype document image analysis system for technical journals[END_REF]. Many other algorithms have been presented since then and surveys have been done in 2000 [START_REF] Nagy | Twenty years of document image analysis in PAMI[END_REF] and in 2003 [START_REF] Mao | Document structure analysis algorithms: a literature survey[END_REF]. In 2007 and 2014, two surveys propose formal definitions and detail the main trends of document segmentation algorithms [START_REF] Namboodiri | Document structure and layout analysis[END_REF][START_REF] Kise | Page segmentation techniques in document analysis[END_REF]. There has also been several competitions and benchmarks providing an overview and a comparison of the state of the art [START_REF] Shafait | Performance evaluation and benchmarking of six-page segmentation algorithms[END_REF][START_REF] Antonacopoulos | ICDAR2009 Page segmentation competition[END_REF][START_REF] Antonacopoulos | Historical document layout analysis competition[END_REF][START_REF] Lamiroy | Document analysis algorithm contributions in end-to-end applications: report on the ICDAR 2011 contest[END_REF][START_REF] Antonacopoulos | Competition on Historical Newspaper Layout Analysis[END_REF][START_REF] Antonacopoulos | Competition on Historical Book Recognition[END_REF][START_REF] Antonacopoulos | ICDAR2015 Competition on recognition of documents with complex layouts[END_REF][START_REF] Murdock | ICDAR 2015 Competition on text line detection in historical documents[END_REF]. However, these papers do not provide a coverage of all the available document image segmentation algorithms.

For the above reasons we present in this article a survey of recent document segmentation algorithms. Our work was motivated by the outstanding and very exhaustive review of natural image segmentation algorithms done by Vantaram and Saber [START_REF] Vantaram | Survey of contemporary trends in color image segmentation[END_REF].

We will first detail the scope of this survey in section 2. Then we propose a typology of document image segmentation algorithms in section 3. The next three sections survey the algorithms. Finally we discuss the limitations, the evaluation, the research trends and the industrial interest of the algorithms in section 7. The data used in this section can be found in the supplementary material. A conclusion completes this paper.

Scope of this survey

We will now detail the three scopes of this survey: the scientific scope (which algorithms are surveyed), the document scope (the type of documents on which they are expected to work) and the publication scope of this survey (for which publications we claim to be exhaustive).

Scientific scope of this survey

Segmentation algorithms can be applied to document images but also to a set of document images (in order to segment a book into its chapters by instance), to natural images [START_REF] Vantaram | Survey of contemporary trends in color image segmentation[END_REF], to medical images [START_REF] Peng | A new convex variational model for liver segmentation[END_REF] and even to 3D meshes [START_REF] Katz | Mesh segmentation using feature point and core extraction[END_REF]. More generally a segmentation algorithm can be viewed as a specific kind of clustering or partitioning algorithm or of classification algorithm when it labels the parts that are segmented.

More formally for the value of each input element I(x) a segmentation algorithm associates a region number or a label J(x) where x is the element index. x can be the page number, the node index, or even the pixel coordinates in an image.

∀x, I(x)

S egmentation

→ J(x) (1)
We only focus on offline document image segmentation algorithms. These algorithms' input excludes the history of the creation of the document such as writing strokes or typing/creation order. This kind of information is usually not available in a document analysis system such as the one described in Figure 1. However, we do not exclude algorithms that use the static image information to compute the document history. Such algorithms have been developed in the past [START_REF] Doermann | Recovery of temporal information from static images of handwriting[END_REF] and in particular in paleography [START_REF] Daniels | A Calligraphic Approach to Aramaic Paleography[END_REF] but none was found during the time frame of this survey. Some algorithms such as some super pixel-based approaches [START_REF] Achanta | SLIC Superpixels compared to state-of-the-art superpixel methods[END_REF] over-segment the images into small chunks that need a post processing merging step to make meaningful parts. These algorithms are not surveyed because they do not perform a complete segmentation on their own.

We include in this survey line segmentation algorithms as long as they explicitly detect the beginning, the end, the top and the bottom of each line. This excludes the algorithms that only draw a border between lines from one side of the page to the other.

Some algorithms are capable of identifying the type of content contained in each area. There are two kinds of identification: the physical layout and the logical layout.

The physical layout relates to the nature of the content such as text, typewritten text, graphics, diagram, picture, decoration, etc. The logical layout relates to the function of the content such as header, footnote, main body, etc. In this survey we focus on algorithms that provide regions without labels or with a physical layout labeling. While we don't exclude algorithms that provide a logical labeling, we do not discuss this capability. This is motivated by the fact that this kind of labeling is usually very specific to a document type or layout and cannot be generalized to other document types. We do not survey algorithms that start from a segmentation result and then label them.

While natural image segmentation algorithms are not made for document images, that does not mean that they cannot perform this task as shown in a recent study [START_REF] Eskenazi | Evaluation of the stability of four document segmentation algorithms[END_REF].

Nevertheless we do not survey them as they are usually not tested on document images.

Neither do we consider the basics of segmentation algorithms. If needed [START_REF] Namboodiri | Document structure and layout analysis[END_REF][START_REF] Kise | Page segmentation techniques in document analysis[END_REF] provide a very good introduction to them.

Typology of documents

Since the main processing step of document analysis relies on extracting or indexing the text that they contain, we have chosen to sort them according to the amount of textual content they have. Figure 2 summarizes the main types of documents from the most textual on the left to the least textual on the right. It is difficult to make a generic and clear classification so the boundaries between the different categories should be considered as fuzzy. By instance, some comics do not contain any text and some magazine pages are only textual.

Music scores are classified as one of the most textual documents because we can consider music writing as a language and thus as textual content. However since the layout of music scores is very constrained it is not a big challenge and no publication was made for analyzing it. Most publications relate to music symbol segmentation, staff removal and direct recognition of music scores without any layout analysis [START_REF] Rebelo | Optical music recognition: state-of-the-art and open issues[END_REF].

There is no specific category for historical documents. This is because all the categories on the figure contain both contemporary and historical documents. Moreover, defining a specific category for historical documents would require defining a boundary between historical and contemporary documents which would most likely not be feasible. The scientific community separates historical from contemporary documents on a subjective case by case basis, mostly because of the degradations and the variability they have and the specific algorithms needed to deal with them. Hence this separation should not be related to the time but to the degradations (and maybe the content) of the document. Similarly to natural scene images, it is not impossible that algorithms made for historical documents perform well on contemporary documents. Actually, many algorithms [START_REF] Du | Text line segmentation in handwritten documents using Mumford-Shah model[END_REF][START_REF] Journet | Document image characterization using a multiresolution analysis of the texture: application to old documents[END_REF][START_REF] Lemaitre | Multiresolution cooperation makes easier document structure recognition[END_REF][START_REF] Louloudis | Text line and word segmentation of handwritten documents[END_REF][START_REF] Lazzara | The SCRIBO Module of the Olena platform : a free software framework for document image analysis[END_REF][START_REF] Fern | Document segmentation using relative location features[END_REF][START_REF] Konya | Adaptive methods for robust document image understanding[END_REF][START_REF] Diem | Text line detection for heterogeneous documents[END_REF][START_REF] Liu | Near-duplicate document image matching: A graphical perspective[END_REF] have been evaluated on both modern and historical documents.

Similarly to the historical documents, handwriting can appear in all categories and as such does not have a category of its own. Moreover, documents that were written before the invention of printing were obviously handwritten but the writing style can be closer to machine print in some cases.

Color wise, there are three main types of color depth: black and white (BW), gray level (GL) and color (C).

We survey all mostly textual documents, the comics, the advertisements and magazines cover pages. We do not survey technical drawings or maps because the mere definition of what is their layout is already a challenge and they usually require very specific tools to be analyzed. We do not exclude an algorithm if it is tested on a data set that includes documents both in and out of the scope of this paper.

Publication scope of this survey

It is hardly possible to survey exhaustively all scientific journals, conferences and publications of the field. We have chosen to survey the algorithms published since 2008 since no survey includes papers after this date. Kise's survey in 2014 [START_REF] Kise | Page segmentation techniques in document analysis[END_REF] -which is mostly and introduction to the field -only cites papers before 2007. We review mostly but not only the papers published in the major venues for the document analysis community for which we claim to be exhaustive (in alphabetical order):

• ACM Symposium on Document Engineering (DocEng),

• Document Recognition and Retrieval (DRR),

• European Conference on Computer Vision (ECCV),

• International Conference on Computer Vision (ICCV),

• IAPR International Conference on Document Analysis and Recognition (IC-DAR),

• IAPR International Workshop on Document Analysis Systems (DAS),

• IEEE Conference on Computer Vision and Pattern Recognition (CVPR),

• IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI),

• International Conference on Pattern Recognition (ICPR),

• International Journal on Document Analysis and Recognition (IJDAR),

• Pattern Recognition (PR),

• Pattern Recognition Letters (PRL)

Typology of segmentation algorithms

Before going through the in-depth survey of segmentation algorithms, it is wise to define a typology to organize them. Document image segmentation algorithms are typically classified into three groups [START_REF] Mao | Document structure analysis algorithms: a literature survey[END_REF][START_REF] Namboodiri | Document structure and layout analysis[END_REF]: top-down, bottom-up and hybrid algorithms.

Top-down algorithms start from the whole page and try to partition it. Bottom up algorithms start from a small scale and try to agglomerate the elements at this scale into bigger elements up to the the scale of the whole document. There are three main scales from which they start: pixels, connected components and "patches" which is a userdefined scale. This classification is very objective but does not reflect the capabilities and limitations of each algorithms. It only reflects the order of information processing.

From a different perspective, Kise [START_REF] Kise | Page segmentation techniques in document analysis[END_REF] classifies first the algorithms according to their capability of segmenting documents with overlapping layouts such as a stamp on top of some text. This allows one to select a suitable algorithm based on the segmentation task at hand. However this typology only considers classification algorithms for segmenting documents with overlapping layouts which is restrictive. Extending this typology for an exhaustive survey would lead to classifying some algorithms in several categories which would make each category and the whole classification less legible.

A given segmentation algorithm may not be able to segment any layout. This is the main limitation of such an algorithm and we use it to classify the surveyed algorithms into three groups. The layout segmentation limitation can come either from the way the algorithm itself works (group one) such as X-Y cut that has been written to segment a specific kind of layout with only horizontal and vertical regions (called Manhattan layout). It can also come from the parameters given to the algorithm (group two) such as Voronoi which is versatile but requires different parameters depending on the document style (font size, noise characteristics, connected component size distribution, etc.). A third group of algorithms attempts to overcome these limitations and could potentially not have any (such as neural networks). The overall algorithm type classification is shown in Figure 3. Thanks to the groups we defined it allows us to represent both the techniques and the limitations of the algorithms. Most algorithms rely on one main technique but also make use of other secondary techniques to obtain intermediate data.

As such, the classification of an algorithm is necessarily fuzzy and we classified each algorithm based on its core technique.

The algorithms in group one

The algorithms of this group were the first to appear. They usually aim at segmenting a specific, predefined kind of layout such as a Manhattan layout for instance.

Hence they can be used without any training. There are three main subcategories in this group:

The algorithms that make clear assumptions about the document layout [START_REF] Murdock | ICDAR 2015 Competition on text line detection in historical documents[END_REF][START_REF] Lemaitre | Multiresolution cooperation makes easier document structure recognition[END_REF][START_REF] Camillerapp | A generic method for structure recognition of handwritten mail documents[END_REF][START_REF] Carton | Automatic and interactive rule inference without ground truth[END_REF][START_REF] Shafait | Structural mixtures for statistical layout analysis[END_REF][START_REF] Shafait | Background variability modeling for statistical layout analysis[END_REF][START_REF] Ouwayed | Multi-oriented text line extraction from handwritten arabic documents[END_REF][START_REF] Liu | Semi-supervised learning for text-line detection[END_REF][START_REF] Ouwayed | General text line extraction approach based on locally orientation estimation[END_REF][START_REF] Papavassiliou | Handwritten document image segmentation into text lines and words[END_REF][START_REF] Ouwayed | A general approach for multi-oriented text line extraction of handwritten documents[END_REF]: they either define this layout with a grammar, a set of rules or they assume that it is a Manhattan layout and use projection profiles.

The algorithms that use filtering techniques to make the document regions appear [START_REF] Bockholt | Document image retrieval with morphology-based segmentation and features combination[END_REF][START_REF] Bukhari | High performance layout analysis of Arabic and Urdu document images[END_REF][START_REF] Bukhari | Improved document image segmentation algorithm using multiresolution morphology[END_REF][START_REF] Lemaitre | A perceptive method for handwritten text segmentation[END_REF][START_REF] Tang | Text line segmentation based on matched filtering and top-down grouping for handwritten documents[END_REF][START_REF] Ferilli | A distance-based technique for non-Manhattan layout analysis[END_REF][START_REF] Shi | A steerable directional local profile technique for extraction of handwritten arabic text lines[END_REF]: They usually rely on RLSA, mathematical morphology or other filters. The filters characteristics reflect the assumptions made on the layout geometry.

The algorithms that try to identify straight lines [START_REF] Louloudis | Text line and word segmentation of handwritten documents[END_REF][START_REF] Chen | Hybrid page segmentation with efficient whitespace rectangles extraction and grouping[END_REF][START_REF] Wang | Comic frame extraction via line segments combination[END_REF]: This can be done with a Hough transform, by trying to identify straight lines or square borders, or by identifying white spaces alignment, in which case the "lines" may be invisible lines.

The algorithms in group two

175 They where the second to appear. Their difference with the algorithms in group one is that they try to adapt to local variations in the document in order to be able to segment a broader range of layouts with the same algorithm. This is achieved by using more flexible algorithms. The counter part of this is usually a higher number of parameters which are difficult to tune and may require training on a large data set.

180

These algorithms are usually only limited by the values assigned to their parameters.

There are four main subcategories in this group:

The clustering algorithms [9-12, 14, 25, 28, 30-32, 51-74]: They are bottom up algorithms and try to cluster elements based on geometric or texture or a more general set of features.

The algorithms based on function analysis [START_REF] Antonacopoulos | ICDAR2015 Competition on recognition of documents with complex layouts[END_REF][START_REF] Murdock | ICDAR 2015 Competition on text line detection in historical documents[END_REF][START_REF] Du | Text line segmentation in handwritten documents using Mumford-Shah model[END_REF][START_REF] Bukhari | Segmentation of curled textlines using active contours[END_REF][START_REF] Bukhari | Coupled snakelet model for curled textline segmentation of camera-captured document images[END_REF][START_REF] Bukhari | Text-line extraction using a convolution of isotropic Gaussian filter with a set of line filters[END_REF][START_REF] Bukhari | Towards generic text-line extraction[END_REF][START_REF] Bukhari | Coupled snakelets for curled text-line segmentation from warped document images[END_REF][START_REF] Bukhari | Script-independent handwritten textlines segmentation using active contours[END_REF][START_REF] Bukhari | Ridges based curled textline region detection from grayscale camera-captured document[END_REF][START_REF] Ryu | Language-independent text-line extraction algorithm for handwritten documents[END_REF][START_REF] Kim | Script-free text line segmentation using interline space model for printed document images[END_REF][START_REF] Shen | Text line extraction in free-style document[END_REF][START_REF] Koo | State estimation in a document image and its application in text block identification and text line extraction[END_REF][START_REF] Yin | A variational bayes method for handwritten text line segmentation[END_REF][START_REF] Cruz | EM-based layout analysis method for structured documents[END_REF]: they mostly rely on function optimization e.g. trying to bring a function as close as possible to an objective value. Some specific cases are active contours, energy minimization and probabilistic layout estimation. They are top-down algorithms. In interesting fact about these algorithms is that while most algorithms work with the region areas, those based on function analysis usually work with the region boundaries.

The classification algorithms [START_REF] Antonacopoulos | ICDAR2009 Page segmentation competition[END_REF][START_REF] Murdock | ICDAR 2015 Competition on text line detection in historical documents[END_REF][START_REF] Fern | Document segmentation using relative location features[END_REF]: they are trained to recognize the different types of elements based on a given set of features (purely texture or more generic features). As a consequence they need training and produce labeled elements.

The regions are made of adjacent elements having the same label hence they are bottom up algorithms.

The algorithms in group three

They appeared last. They try to overcome the limitations of the other algorithms by combining them or by using artificial intelligence. Thus they cannot be considered as bottom-up or top-down algorithms. There are three subcategories in this group:

The hybrid algorithms [START_REF] Antonacopoulos | ICDAR2009 Page segmentation competition[END_REF][START_REF] Antonacopoulos | ICDAR2015 Competition on recognition of documents with complex layouts[END_REF][START_REF] Murdock | ICDAR 2015 Competition on text line detection in historical documents[END_REF][START_REF] Smith | Hybrid page layout analysis via tab-stop detection[END_REF][START_REF] Barlas | A typed and handwritten text block segmentation system for heterogeneous and complex documents[END_REF][START_REF] Asi | Simplifying the reading of historical manuscripts[END_REF][START_REF] Wang | Text line extraction in document images[END_REF] combine several other algorithms in symbiosis: While they could potentially accumulate the strength of several other algorithms, some of them tend to be very complex without significant performance or versatility improvement.

The combination algorithm (only one has been presented) [START_REF] Stamatopoulos | A method for combining complementary techniques for document image segmentation[END_REF] combines the results of several algorithms to effectively improve them.

The neural network algorithms [START_REF] Murdock | ICDAR 2015 Competition on text line detection in historical documents[END_REF][START_REF] Moysset | Paragraph text segmentation into lines with recurrent neural networks[END_REF] make use of artificial intelligence to automatically learn significant features and perform the required task. They need careful design and are subject to over training. They also tend to be a "black box" whose functioning is not easily explained.

Layout constrained by the algorithm (Group one)

The algorithms in this group are such that their internal mechanisms limit the variety of layouts that they can segment.

Segmentation based on document structure assumption

These algorithms are the most limited ones. They are made for a very specific type of layout hence they are only applicable to documents with a structured layout. This drawback is counterbalanced by their success rate in segmenting this specific layout in comparison with other more flexible techniques. They are also extremely fast.

Grammar

There are five algorithms of this type [START_REF] Lemaitre | Multiresolution cooperation makes easier document structure recognition[END_REF][START_REF] Camillerapp | A generic method for structure recognition of handwritten mail documents[END_REF][START_REF] Carton | Automatic and interactive rule inference without ground truth[END_REF][START_REF] Shafait | Structural mixtures for statistical layout analysis[END_REF][START_REF] Shafait | Background variability modeling for statistical layout analysis[END_REF]. They were first published in 2006

by Coüasnon [START_REF] Coüasnon | DMOS, a generic document recognition method: application to table structure analysis in a general and in a specific way[END_REF] and tested on a data set of 88745 documents which is an unrivaled data set size. He designed a layout grammar language called DMOS. This language can describe any layout and the associated parser recognizes this layout in an image.

The grammar also allows the association of a label to each region of the layout thus producing a labeled segmentation. Lemaitre et al. improved it in 2008 [START_REF] Lemaitre | Multiresolution cooperation makes easier document structure recognition[END_REF] by adding a multi resolution approach which made it flexible enough to segment handwritten letters (provided that their layout obeyed certain rules) and to identify text lines in administrative documents in French and Bangla. Carton et al. [START_REF] Carton | Automatic and interactive rule inference without ground truth[END_REF] continued this work with an interactive training step capable of creating automatically an exhaustive set of models for a large data set.

Shafait et al. [START_REF] Shafait | Structural mixtures for statistical layout analysis[END_REF], proposed another grammar algorithm based on a probabilistic layout formulation. The user defines a set of cuts (only horizontal and vertical in the paper) whose position is defined approximately. Then for each image a probabilistic fitting is performed to obtain the appropriate regions. This algorithm is capable of segmenting tight layouts with very small margins. Its results are not compared with those of DMOS.

Projection profiles

There are 7 algorithms of this type [START_REF] Ouwayed | Multi-oriented text line extraction from handwritten arabic documents[END_REF][START_REF] Liu | Semi-supervised learning for text-line detection[END_REF][START_REF] Ouwayed | General text line extraction approach based on locally orientation estimation[END_REF][START_REF] Papavassiliou | Handwritten document image segmentation into text lines and words[END_REF][START_REF] Ouwayed | A general approach for multi-oriented text line extraction of handwritten documents[END_REF] and the two CASIA algorithms published in [START_REF] Murdock | ICDAR 2015 Competition on text line detection in historical documents[END_REF]. Ouwayed and Belaid [START_REF] Ouwayed | A general approach for multi-oriented text line extraction of handwritten documents[END_REF] use projection profiles to segment multi-oriented, text only documents. They make a paving of the document with rectangles.

Then they compute the projection profile of each rectangle along several directions.

The direction with the highest maximum of Wigner-Ville distribution is that of the text.

Then, they use heuristics combined with local projection profiles to detect regions with non homogenous text orientation and text lines. They are also capable of segmenting curved text lines. Another feature of the algorithm is the capability to separate intricate text lines but this costs the generality of the algorithm as it requires typographic heuristics specific to Arabic handwriting.

Liu and al. [START_REF] Liu | Semi-supervised learning for text-line detection[END_REF] use [START_REF] Ouwayed | A general approach for multi-oriented text line extraction of handwritten documents[END_REF] to segment Manhattan layouts. After a binarization that replaces text lines by black regions, they use projection profiles to remove border noise and detect text columns. The interest of the algorithm lies in the noise removal process.

It first classifies the text lines into two levels of confidence. Then based on the most confident ones, it computes its internal feature parameters on the fly. These features help discriminate the lines as noise or text lines. The algorithm improves significantly the state of the art and is evaluated on 1922 documents containing four representative languages: Arabic, English, Chinese and Yiddish.

Segmentation based on filtering algorithms

These algorithms usually use specific predefined filters to segment a given type of content. They frequently rely on assumptions that the text lines are straight and/or horizontal.

Mathematical morphology

Six algorithms using mathematical morphology have been published [START_REF] Bockholt | Document image retrieval with morphology-based segmentation and features combination[END_REF][START_REF] Bukhari | High performance layout analysis of Arabic and Urdu document images[END_REF][START_REF] Bukhari | Improved document image segmentation algorithm using multiresolution morphology[END_REF][START_REF] Lemaitre | A perceptive method for handwritten text segmentation[END_REF][START_REF] Tang | Text line segmentation based on matched filtering and top-down grouping for handwritten documents[END_REF][START_REF] Ferilli | A distance-based technique for non-Manhattan layout analysis[END_REF]. Bockholt et al. [START_REF] Bockholt | Document image retrieval with morphology-based segmentation and features combination[END_REF] use several combinations of erosion and dilation to efficiently identify successively the pictures, the graphics and the text. While being a basic type of processing it proves very efficient for the task of document retrieval.

Ferili et al. [START_REF] Ferilli | A distance-based technique for non-Manhattan layout analysis[END_REF] replace the logical AND of RLSA by an OR. This makes the algorithm more computationally efficient as only one run length is performed. They make the assumption that the text is horizontal. An interesting addition is the extension of the algorithm to natively digital documents based on their basic blocks.

Buckhari et al. [START_REF] Bukhari | Improved document image segmentation algorithm using multiresolution morphology[END_REF] use Bloomberg's segmentation algorithm [START_REF] Bloomberg | Multiresolution morphological approach to document image analysis[END_REF] which is based on mathematical morphology. They add a first step to merge broken horizontal and vertical lines with a hit-miss morphological transform and a second step to fill holes.

Filtering

The only contribution for this kind of algorithm was done by Shi et al. [START_REF] Shi | A steerable directional local profile technique for extraction of handwritten arabic text lines[END_REF]. It was reused by A2iA in a competition [START_REF] Murdock | ICDAR 2015 Competition on text line detection in historical documents[END_REF] where it was ranked third out of 7 participants. The method is based on steerable filters (filters that can be rotated) to detect text lines along five orientations. A heuristic post processing is used to solve the issue of connected components spanning several lines.

Segmentation based on straight line identification algorithms

Three contributions are based on straight line identification [START_REF] Louloudis | Text line and word segmentation of handwritten documents[END_REF][START_REF] Chen | Hybrid page segmentation with efficient whitespace rectangles extraction and grouping[END_REF][START_REF] Wang | Comic frame extraction via line segments combination[END_REF]. Louloudis et al. [START_REF] Louloudis | Text line and word segmentation of handwritten documents[END_REF] split the connected components horizontally into blocks based on the average character height. This allows the algorithm to work on handwritten text where several characters are merged into one connected component. However the horizontal partitioning assumes that the text is also horizontal. Once this partitioning is done, they apply a Hough transform on the centers of gravity of each block to detect text lines.

Wang et al. [START_REF] Wang | Comic frame extraction via line segments combination[END_REF] attempt to reconstruct the border of the frames in comic books in order to segment them. Their algorithm is able to segment frames with only two apparent borders but is limited to quadrangle regions. They separate the background then they use the Douglas-Peucker algorithm [START_REF] Douglas | Algorithms for the reduction of the number of points required to represent a digitized line or its caricature[END_REF] to fit quadrangles onto the candidate frames. This is followed by a classification of the frame complexity and specific heuristics are used to complete the frame border. This algorithm only improves the state of the art for difficult to very difficult layouts which is its original goal.

Chen et al. [START_REF] Chen | Hybrid page segmentation with efficient whitespace rectangles extraction and grouping[END_REF] analyze the white spaces to segment the document into text columns. The connected components are grouped into horizontal chains to create white spaces between these chains. Then the white spaces are grouped vertically to make white lines/column separators. The algorithm works well to detect text but not for graphical parts. It won the two segmentation competitions of ICDAR 2013 [START_REF] Antonacopoulos | Competition on Historical Newspaper Layout Analysis[END_REF][START_REF] Antonacopoulos | Competition on Historical Book Recognition[END_REF].

Layout constrained by the parameters (Group two)

This group contains the majority of algorithms that have been published. They remain fairly simple while being flexible enough to address a wide range of problems.

Segmentation based on clustering

This is clearly the most popular type of algorithm with 40 algorithms. Mehri et al [START_REF] Mehri | Texture feature evaluation for segmentation of historical document images[END_REF] demonstrate that Gabor texture features outperform auto-correlation and co-occurrence texture features.

Generic feature clustering

Six algorithms use several types of features [START_REF] Carel | Multiresolution approach based on adaptive superpixels for administrative documents segmentation into color layers[END_REF][START_REF] Kumar | Handwritten arabic text line segmentation using affinity propagation[END_REF][START_REF] Ziaratban | An adaptive script-independent block-based text line extraction[END_REF][START_REF] Chen | A multi-plane approach for text segmentation of complex document images[END_REF][START_REF] Agrawal | Voronoi++: a dynamic page segmentation approach based on Voronoi and Docstrum features[END_REF][START_REF] Agrawal | Context-aware and content-based dynamic Voronoi page segmentation[END_REF]. The most outstanding one is that of Chen and Wu [START_REF] Chen | A multi-plane approach for text segmentation of complex document images[END_REF]. Roughly, they cut the document into blocks which are then multi-thresholded to create several layers. The connected components of each layer are identified and grouped across blocks based on a predefined set of features.

The evaluation data set is small (65 documents) but very challenging as it contains only magazine covers and advertisements that are multi-layered color documents with uneven background. They outperform significantly the state of the art and achieve both precision and recall above 99% for text extraction.

Carel [START_REF] Carel | Multiresolution approach based on adaptive superpixels for administrative documents segmentation into color layers[END_REF] uses a multi-resolution color and spatial clustering to identify the color layers contained in a document and the connected components in each layer.

Segmentation based on function analysis

Sixteen algorithms rely on function analysis techniques. They have the advantage that, based on the "flexibility" of the functions, one can select how much they will follow the contours of the elements to segment. This can be helpful if we want to have a rough outline of the document regions or if we want to segment precise elements such as warped text lines.

Active contours

Function optimization

Seven algorithms use function optimization [START_REF] Antonacopoulos | ICDAR2015 Competition on recognition of documents with complex layouts[END_REF][START_REF] Murdock | ICDAR 2015 Competition on text line detection in historical documents[END_REF][START_REF] Du | Text line segmentation in handwritten documents using Mumford-Shah model[END_REF][START_REF] Ryu | Language-independent text-line extraction algorithm for handwritten documents[END_REF][START_REF] Kim | Script-free text line segmentation using interline space model for printed document images[END_REF][START_REF] Shen | Text line extraction in free-style document[END_REF][START_REF] Koo | State estimation in a document image and its application in text block identification and text line extraction[END_REF]. They usually define a cost or energy function which needs to be minimized. So far, they work best for text line segmentation although the ISPL method was second in the last ICDAR document segmentation competition [START_REF] Antonacopoulos | ICDAR2015 Competition on recognition of documents with complex layouts[END_REF]. The state of the art with this technique is held by Ryu et al. [START_REF] Ryu | Language-independent text-line extraction algorithm for handwritten documents[END_REF] which also won the ICDAR 2013 Competition for handwriting segmentation [START_REF] Stamatopoulos | ICDAR 2013 Handwriting segmentation contest[END_REF] and 2015 Competition on text line detection [START_REF] Murdock | ICDAR 2015 Competition on text line detection in historical documents[END_REF]. Their contribution resides in over-segmenting connected components that do not fit a normalization criteria. From this they obtain a better estimation of the belonging of each connected component to a given text line which in turn allows them to build a better cost function.

The optimization of this function is improved with dynamic programming. The over segmented components are then merged into proper components.

Shen et al. [START_REF] Shen | Text line extraction in free-style document[END_REF] use both intra and interline metrics to build a segmentation cost function. After an initial geometric clustering they perform a simulated annealing optimization. This means that the probability of accepting a new segmentation that increases the cost function is not null but decreases with each iteration. Combined with a custom binarization, this allows them to extract text line from challenging color documents with non uniform background (CD covers) or unusual layout (business cards).

Kim and Oh [START_REF] Kim | Script-free text line segmentation using interline space model for printed document images[END_REF] highlight the interest of using interline information over intra-line information for Asian scripts.

Probabilistic layout estimation

Two algorithms make a probabilistic estimation of the layout [START_REF] Yin | A variational bayes method for handwritten text line segmentation[END_REF][START_REF] Cruz | EM-based layout analysis method for structured documents[END_REF] but do not bring a significant improvement. Yin and Liu [START_REF] Yin | A variational bayes method for handwritten text line segmentation[END_REF] perform an estimation of the number of text lines with a blur filter and then use a variational Bayes approach to segment the image rescaled at 75 dpi. This improves slightly the state of the art on a large but not very challenging data set.

Cruz and Terrades [START_REF] Cruz | EM-based layout analysis method for structured documents[END_REF] proposed a method based on Conditional Random Field (CRF) and location features similar to [START_REF] Fern | Document segmentation using relative location features[END_REF] (see section 5.3.2) but without any improvement over the state of the art. This work is at the crossing between optimizing a probabilistic layout estimation and a classification.

Segmentation based on classification

This is the second most popular type of algorithms with 30 algorithms. A noticeable difference in the scientific work when compared with the clustering is the fact that classification algorithms all require training.

Texture classification

Three algorithms use only texture features [START_REF] Antonacopoulos | ICDAR2009 Page segmentation competition[END_REF][START_REF] Benjelil | Complex documents images segmentation based on steerable pyramid features[END_REF][START_REF] Baechler | Multi resolution layout analysis of medieval manuscripts using dynamic MLP[END_REF]. Baechler and Ingold [START_REF] Baechler | Multi resolution layout analysis of medieval manuscripts using dynamic MLP[END_REF] string together three Dynamic Multi-Layer Perceptrons (DMLP) at three resolutions to segment historical documents. Each DMLP uses the label output of the DMLP at a lower resolution plus texture features at its resolution. Each level processes only part of the labels produced by the lower level in order to refine these specific labels.

Feature classification

Most classification algorithms (24 out of 27) use a generic set of features.

Black and white algorithms. Among them, 12 use only binary images [START_REF] Antonacopoulos | ICDAR2009 Page segmentation competition[END_REF][START_REF] Fern | Document segmentation using relative location features[END_REF][START_REF] Peng | Markov random field based text identification from annotated machine printed documents[END_REF][START_REF] Sarkar | Classifying foreground pixels in document images[END_REF][START_REF] Bukhari | Document image segmentation using discriminative learning over connected components[END_REF][START_REF] Pinson | Connected component level discrimination of handwritten and machineprinted text using eigenfaces[END_REF][START_REF] Peng | Using a boosted tree classifier for text segmentation in hand-annotated documents[END_REF][START_REF] Benjlaiel | Multi-oriented handwritten annotations extraction from scanned documents[END_REF][START_REF] Le | Text and non-text segmentation based on connected component features[END_REF][START_REF] Yamaguchi | Feature extraction for document image segmentation by pLSA model[END_REF][START_REF] Hebert | Continuous CRF with multi-scale quantization feature functions application to structure extraction in old newspaper[END_REF][START_REF] Peng | Handwritten text separation from annotated machine printed documents using Markov random fields[END_REF].

Peng [START_REF] Peng | Handwritten text separation from annotated machine printed documents using Markov random fields[END_REF] and Pinson [START_REF] Pinson | Connected component level discrimination of handwritten and machineprinted text using eigenfaces[END_REF] focus on extracting overlapping handwritten and typewritten text. Pinson and Barret's algorithm [START_REF] Pinson | Connected component level discrimination of handwritten and machineprinted text using eigenfaces[END_REF] Bukhari [START_REF] Bukhari | Document image segmentation using discriminative learning over connected components[END_REF] focus on extracting text from documents that contain graphics illustrations such as circuit drawings. The challenge here is to identify correctly text and graphics. While the challenge seems easier than separating overlapped typewritten and handwritten text, many segmentation algorithms do not handle graphics well. Thus targeting this specific issue is a good addition to the state of the art. To do this, they rescale every connected component to a predefined size and do the same with a wider image centered on the connected component in order to capture its context. Then they use a Multi-Layer Perceptron (MLP) to do the classification. The recall for text and non-text (graphic) is consistently above 93 and 96% respectively on 100 documents.

Fern [START_REF] Fern | Document segmentation using relative location features[END_REF] focuses on extracting the regions of structured documents. They use Gabor (texture) features with a CRF. Their contribution lies in the addition of relative location features which are the probability of a region being of a certain class given its position relatively to the regions of the other classes. These features (one per class and per region) have a significant impact for segmenting structured documents. The improvement remains less significantly on non structured documents.

Gray-level algorithms. Four algorithms use gray level information [START_REF] Zhong | Tensor representation learning based image patch analysis for text identification and recognition[END_REF][START_REF] Montreuil | Unconstrained handwritten document layout extraction using 2D conditional random fields[END_REF][START_REF] Diem | Text classification and document layout analysis of paper Fragments[END_REF][START_REF] Garz | Layout analysis for historical manuscripts using SIFT features[END_REF]. Diem [START_REF] Diem | Text classification and document layout analysis of paper Fragments[END_REF] tackles the challenge of segmenting document fragments. After extracting candidate word blobs with projection profiles, they introduce Gradient Shape Features (GSF) to refine the segmentation and classify the text as handwritten or typewritten with a support vector machine (SVM). GSF are computed on a sliding window scaled to the size of the word blob. For a given window they are similar to shape context features applied on the inverted gradient image instead of the original image. Then they perform a geometric clustering of the word blobs into lines. A final global voting with another SVM classifies the candidate lines into typewritten or handwritten again.

They include an error back-propagation to relabel the word blobs that were mistakenly labeled. They improve the state of the art for graphics classification while maintaining a similar performance on the text in ICDAR 2009 segmentation competition [START_REF] Antonacopoulos | ICDAR2009 Page segmentation competition[END_REF].

Zhong and Cheriet [START_REF] Zhong | Tensor representation learning based image patch analysis for text identification and recognition[END_REF] devise a new tensor-based learning algorithm and apply it successfully to classify text and non text (borders, noise, background, etc.) on text only ancient manuscripts.

Color algorithms. Eight feature classification algorithms use color information [START_REF] Murdock | ICDAR 2015 Competition on text line detection in historical documents[END_REF][START_REF] Wang | Document content extraction using automatically discovered features[END_REF][START_REF] Baechler | Text line extraction using DMLP classifiers for historical manuscripts[END_REF][START_REF] Wei | Evaluation of SVM, MLP and GMM classifiers for layout analysis of historical documents[END_REF][START_REF] Chen | Robust text line segmentation for historical manuscript images using color and texture[END_REF][START_REF] Fischer | A combined system for text line extraction and handwriting recognition in historical documents[END_REF][START_REF] Chen | Page segmentation of historical document images with convolutional autoencoders[END_REF][START_REF] Garg | A CRF based scheme for overlapping multi-colored text graphics separation[END_REF]. Garg et al. [START_REF] Garg | A CRF based scheme for overlapping multi-colored text graphics separation[END_REF] separate text and graphics in challenging magazine covers.

They use an SVM to classify Gabor and edge features followed by a CRF to include the local spatial context. The the CRF improves the performance by 2 points.

Wei et al. [START_REF] Wei | Evaluation of SVM, MLP and GMM classifiers for layout analysis of historical documents[END_REF] compare the performance of SVM, MLP and GMM (Gaussian mixture model) classifiers. They find that SVM and MLP outperform GMM but cannot conclude which one is best. This depends on the data. The dependency on the features is not studied.

Wang et al. [START_REF] Wang | Document content extraction using automatically discovered features[END_REF] make a very interesting contribution by finding a way to automatically discover features to improve the performance of a 2-nearest neighbor classifier.

Given a large set of features, they sample the feature space. From this sample they find a cluster of errors and project it into the quotient space with the already discovered features. Then they compute a new feature in this hyperspace with a linear combination of the already existing features.

We finish this section with an algorithm on the border between classification and neural networks (which belongs to the third group). Chen et al. [START_REF] Chen | Page segmentation of historical document images with convolutional autoencoders[END_REF] use convolutional autoencoders (a kind of neural network) to automatically discover distinctive features on image patches at three scales and train an SVM with these features. In their evaluation they demonstrate the usefulness of combining these features and their superiority to handcrafted features.

Layout potentially unconstrained (Group three)

This last group contains eleven algorithms with a majority of them published since 2014. These algorithms try to overcome the shortcoming of the others by hybridizing them, combining them or with advanced neural networks.

Segmentation based on hybrid techniques

A large majority of them make several techniques work in symbiosis to obtain better results [START_REF] Antonacopoulos | ICDAR2009 Page segmentation competition[END_REF][START_REF] Antonacopoulos | ICDAR2015 Competition on recognition of documents with complex layouts[END_REF][START_REF] Murdock | ICDAR 2015 Competition on text line detection in historical documents[END_REF][START_REF] Smith | Hybrid page layout analysis via tab-stop detection[END_REF][START_REF] Barlas | A typed and handwritten text block segmentation system for heterogeneous and complex documents[END_REF][START_REF] Asi | Simplifying the reading of historical manuscripts[END_REF][START_REF] Wang | Text line extraction in document images[END_REF]. The most recent significant work was the MHS method developed by Tran et al. which won the last ICDAR complex document segmentation competition [START_REF] Antonacopoulos | ICDAR2015 Competition on recognition of documents with complex layouts[END_REF]. It works by iteratively classifying connected components based on multi-level homogenous regions and white space analysis.

Another significant contribution is the one by Barlas et al. [START_REF] Barlas | A typed and handwritten text block segmentation system for heterogeneous and complex documents[END_REF] which can segment an extremely diverse and complex range of documents in several languages. They generate a feature codebook with self-organizing maps which serves to describe the training set and then train an MLP. Once they have obtained the class layers, they create regions by combining RLSA and white space analysis. They tested it on 1000 documents from the Maurdor data set with three classes (graphics, typewritten and handwritten text) and won the evaluation campaign.

Wang et al. [START_REF] Wang | Text line extraction in document images[END_REF] propose another algorithm for extracting text lines from complex documents with multi-oriented text in several languages. They use MSER to extract candidate characters which are then classified as text or non text with a fast Adaboost classifier. The low confidence text is further evaluated with a Convolutional Neural Network (CNN). The next step is a coarse line extraction with geometrical grouping based on a linearity constraint. This graph is refined by a minimum spanning tree. The last step is an energy minimization refinement of the lines.

Segmentation based on algorithm combination

The only contribution to this type of algorithm was done by Stamatopoulos et al. [START_REF] Stamatopoulos | A method for combining complementary techniques for document image segmentation[END_REF]. They devise a procedure to significantly improve the performance of individual segmentation algorithms by combining their results. The procedure is based on the overlap of the regions produced by the algorithms. They are considered as good above 90% overlap. They use the regions that have more than 70% to compute the values of a task based set of features. All regions below 90% undergo a splitting based on their intersection followed by a merging starting from the regions with the highest overlap. This is successfully applied to text lines segmentation and improve single algorithm results by 15 to 25% depending on the metric.

Segmentation based on neural networks

Two algorithms use neural networks [START_REF] Murdock | ICDAR 2015 Competition on text line detection in historical documents[END_REF][START_REF] Moysset | Paragraph text segmentation into lines with recurrent neural networks[END_REF]. The A2iA1 in the text line segmentation competition [START_REF] Murdock | ICDAR 2015 Competition on text line detection in historical documents[END_REF] did not won it and it is similar to that of Moysset et al. [START_REF] Moysset | Paragraph text segmentation into lines with recurrent neural networks[END_REF] which seems to have improved it. They normalize the width of a text column (or of a text only single column document) and use a bidirectional long-short term memory neural network (BLSTM) to detect text lines and paragraphs. They tackle the issue of modeling gaps and interlines and conclude that each should have its own class. They also show that using specialized neural networks trained on a specific set is better than using a single system trained on a more varied data set.

Discussion

In this section we discuss the applicability scope of the surveyed algorithms, the evaluation practices of the community, its general trends. Finally we quickly review the surveyed algorithms from a user's point of view.

Remarks on the applicability of the surveyed algorithms

When choosing a segmentation algorithm there are a few important remarks to have in mind as they may impact its suitability for a given task.

As a general rule, all segmentation algorithms are script independent e.g. their performance does not depend on the language of the document. Yet they frequently make the assumptions that a language is made of disjoint characters and that each character is made of one connected component. These assumptions are not true for handwritten text and for several languages. Thus the script independence of an algorithm may be limited to scripts that satisfy one or both of the above assumptions.

Many algorithms working on binary images assume that the image is the result of a thresholding process similar to Otsu binarization. They usually do not work on binarization techniques that use error diffusion (dithering). In this case, the image should first be converted to gray level and then appropriately binarized. Figure 4 shows the difference between these two types of binarization. Also, most analyzes based on connected components require binary images.

One may think that being able to segment curved text is better than only straight lines. While this is generally true, it can also lead to merging straight lines that are close to each other and only separated by their orientation. Regarding the processing speed and independently from the implementations that can drastically impact it, bottom-up algorithms are usually slower than top down algorithms and the smaller their processing level, the slower they are. This is illustrated by the fact that there are many more pixels than connected components in an image. The more items there are to process the longer the processing will be.

Although most papers specify parameters in pixels it is better to use the resolution of the test data set to convert these parameters in absolute units such as millimeters.

This will make the algorithm resolution independent and more versatile.

Evaluation of segmentation algorithms

Evaluating and comparing the performance of an algorithm is a difficult task. We summarize here the current state of the art for the evaluation of document segmentation algorithms. A first remark that can be made in the light of all the surveyed papers is that many authors tend to compare their algorithms with other algorithms based on the same technique. This prevents any cross-technique comparison to estimate which techniques are the most promising. Competitions and contest try to remedy this but it would be good if the community could base its future evaluation on the comparison with the best algorithms having the same functionality instead of the same technique.

Existing benchmarks

There has been three independent industry lead benchmarks: the MADCAT program1 by DARPA, RIMES2 by A2iA which is a document analysis company and MAURDOR3 led by the French equivalent of DARPA, the DGA. MADCAT aims at creating a system to automatically categorize and translate any document into English.

RIMES is a data set of handwritten letters that has been used for several competitions [START_REF] Grosicki | ICDAR 2009 Handwriting recognition competition[END_REF][START_REF] Grosicki | ICDAR 2011 French handwriting recognition competition[END_REF]. The most comprehensive one is clearly the MAURDOR campaign and it is publicly available 4 . It contains more than 8000 color documents with a complete ground-truth (regions, region type, contained text, text type, text language and other meta data) as well as ready to use evaluation tools. It contains all types of document except for comics and in French, English and Arabic typewritten and handwritten text.

ICDAR also organizes recurrent document segmentation competitions [START_REF] Antonacopoulos | ICDAR2009 Page segmentation competition[END_REF][START_REF] Antonacopoulos | Historical document layout analysis competition[END_REF][START_REF] Lamiroy | Document analysis algorithm contributions in end-to-end applications: report on the ICDAR 2011 contest[END_REF][START_REF] Antonacopoulos | Competition on Historical Newspaper Layout Analysis[END_REF][START_REF] Antonacopoulos | Competition on Historical Book Recognition[END_REF][START_REF] Antonacopoulos | ICDAR2015 Competition on recognition of documents with complex layouts[END_REF][START_REF] Murdock | ICDAR 2015 Competition on text line detection in historical documents[END_REF]. Unfortunately they frequently use a data set that is too small (below 100 documents) and the evaluation tool is closed source, does not allow processing documents in batch mode and contains numerous parameters which may make the evaluation less objective [START_REF] Antonacopoulos | ICDAR2009 Page segmentation competition[END_REF][START_REF] Antonacopoulos | Historical document layout analysis competition[END_REF][START_REF] Antonacopoulos | Competition on Historical Newspaper Layout Analysis[END_REF][START_REF] Antonacopoulos | Competition on Historical Book Recognition[END_REF][START_REF] Antonacopoulos | ICDAR2015 Competition on recognition of documents with complex layouts[END_REF]. The competition by Murdock et al. [START_REF] Murdock | ICDAR 2015 Competition on text line detection in historical documents[END_REF] is a very good addition as it comes from the industry and thus aims at addressing real case scenario issues. The competition that was organized by Lamiroy et al. [START_REF] Lamiroy | Document analysis algorithm contributions in end-to-end applications: report on the ICDAR 2011 contest[END_REF] adopted an interesting point of view in that it divided an end to end system in several steps for which submissions could be made. Then the contribution of each algorithm was evaluated with the improvement it brought to the overall system.

Data sets

The evaluations in the different surveyed papers raise the question of the exhaustivity of the data sets. Clearly, the state of the art is the MAURDOR data set. Yet it does not contain Asian or Cyrillic scripts. Historical documents are also missing. For these, the St. Gall, Parzival and Washington triptych [START_REF] Baechler | Text line extraction using DMLP classifiers for historical manuscripts[END_REF][START_REF] Wei | Evaluation of SVM, MLP and GMM classifiers for layout analysis of historical documents[END_REF][START_REF] Chen | Robust text line segmentation for historical manuscript images using color and texture[END_REF][START_REF] Chen | Page segmentation of historical document images with convolutional autoencoders[END_REF] 5 is recommended as it covers a wide time span. Adding copies of the same documents could allow the evaluation of the stability of segmentation algorithms as done in [START_REF] Eskenazi | Evaluation of the stability of four document segmentation algorithms[END_REF]. A last addition could be documents similar to comics such as those in [START_REF] Wang | Comic frame extraction via line segments combination[END_REF][START_REF] Rigaud | Robust Frame and Text Extraction from Comic Books[END_REF] In section 2.2 we highlighted the difficulty of defining what is a historical document. A 16 th century manuscript is not the same as a decree from the 19 th century, yet both are historical documents. The exhaustivity in that regard should be considered with the sampling of documents in time not just sampling two classes of documents.

The testing data sets do not all have the same exhaustivity. Clustering algorithms are evaluated on data sets that are, on average, six times bigger than those used for classification algorithms. This is explained by the fact that classification algorithms require large training data sets in particular because of the curse of dimensionality.

Thus for the same total data set size (training + testing) a clustering algorithm will usually be tested on a larger data set. However, this does not change the fact that, because of the testing data set size, the results obtained for clustering algorithms are more reliable than those for classification algorithms.

Moreover, Baird and Casey [START_REF] Baird | Towards versatile DAS[END_REF] advocate for versatile algorithms. These are algorithms capable of dealing with a wide range of documents. Thus, they will have to handle documents that they have not encountered before. Hence the training set should definitely not be bigger than the testing set and the classical k-fold evaluation and data sets that specify training and testing sets need to be updated accordingly.

Metrics

Most evaluations are based on the same principles of counting: false alarms (adding a region), misses (removing a region), merges (two or more regions in one), splits (one region in two or more) and matches (properly segmented region). Algorithms that tend to merge (respectively split) regions are said to under-segment (respectively oversegment) the documents. This is the most reasonable way to evaluate the performance of an algorithm on a single document. However this kind of metric does not evaluate the repeatability and performance stability of the algorithm over a range of documents.

Baird and Casey [START_REF] Baird | Towards versatile DAS[END_REF] denote this as evaluation based on "confidence before accuracy".

We actually analyzed the repeatability of four state of the art segmentation algo- rithms [START_REF] Eskenazi | Evaluation of the stability of four document segmentation algorithms[END_REF] and found that they all have a very poor stability. This is to be expected since they where never evaluated with this criteria but we hope that it will be used in future evaluations.

Trends and statistics

This survey gave us a very good insight on the trends, strengths and weaknesses of current algorithms. Figure 5a shows the main publishing venues.ICDAR stands as the flagship conference of the community. DAS is the second biggest venue of the community and its main journals are PR and IJDAR.

Figure 5b shows the detailed number of algorithms that studied each language and document type. The algorithms have been applied to 19 languages and scripts. This supports the worldwide applicability of the findings of the document analysis community. The top 5 most studied languages are in decreasing order: English, German, French, Arabic and Chinese. Regarding the document types, newspapers and journals have been studied twice as much as any other type. The least studied types are magazine cover pages and comics. Figures 6c and6d show the proportion of algorithms that use a specific color depth and the proportion of algorithms that are evaluated on historical, modern or both types of documents. More and more algorithms make use of color information and are evaluated on historical documents. Currently there is a tie between testing on modern or historical documents. Testing on both types of documents (historical and modern) has a significant share although it seems to become less active.

Figure 7 summarizes the number of publications that have been tested on a given number of different document types (according to the typology of section 2.2) and of different languages for a given data set size. We can see with the big blue and red bubbles that most algorithms that are tested on a data set below 1000 images are only This survey reviewed the algorithms from a scientific stand point. We would now like to see them from a user/industrial perspective. This would be the place for a qualitative analysis of the algorithms in order to identify which ones may be the most suitable for a given task. However the lack of cross-technique comparison and of di-

Conclusion

In this survey we give a complete and yet thorough overview of the current state of the art for document image segmentation. We have seen the major trends for the techniques and the challenges that are tackled. It appears that the community is very dynamic and has extended its area of research to every conceivable problem from "simple" fully constrained documents to the most complicated ones that may seem impossible to segment.

The techniques have also evolved. From the first algorithms that were dedicated to a specific type of document, we have moved towards fully flexible algorithms capable of handling a wide range of layouts and that are nearly fully language independent. Some improvements still remain to be done in particular on three topics: the versatility of the algorithms, their stability and their cross-technique comparison. The training and testing data sets need to be extended to include an even wider range of documents and languages. At the same time, the size balance between the training and the testing set should be reversed in favor of the testing set. These two measures will increase the versatility of the algorithms. The stability of the algorithms has not been much investigated and should be included in future work as current algorithms are not stable. Finally, algorithms should be compared with the best other algorithms that have the same functionality independently from their underlying technique. This will allow a proper identification of the best solution(s) for a given problem.

The recurrent organization of competitions is a very good way to establish a state of the art and a strength of this community. We can be grateful to the organizers and the competitors for contributing in that way to the scientific excellence of the community.

This excellence is also reflected by the strong involvement of industrial partners that recognize the expertise of the document image analysis community. A significant part of the contributions and of the benchmarks was done by them. They regularly provide real world data which allows a more reliable evaluation of the algorithms as their performance is usually much worse on real data sets than on experimental data sets.

This is also why we added a functionality/requirement summary. A proper qualitative analysis could not be done because of the remarks that we made on the evaluation of the algorithms but we hope that in a near future it will become feasible.

For the future we can expect algorithms to make an even wider use of neural networks. The automated discovery of features is also a promising field of research in particular when combined with a multi-scale analysis. It is also clear that future state of the art algorithm will make use of the full color information in order to handle the most challenging documents.

Figure 1 :

 1 Figure 1: A classical document content extraction process

Figure 2 :

 2 Figure 2: Document typology by increasing amount of text from left to right.

Figure 3 :

 3 Figure 3: Typology of document segmentation algorithms. We also specify top-down (TD) and bottom-up (BU) algorithms.

5. 1 . 1 .

 11 schemes and consistently outperforms Voronoi and Voronoi++.Gaceb et al.[START_REF] Gaceb | Application of graph coloring in physical layout segmentation[END_REF] use a custom binarization optimized for fast processing. They take a very novel stand in trying not to group dissimilar connected components. They do this

  All these techniques were proposed by. Their work can be considered as the state of the art for text line extraction based on active contours. It works by adding coupled snakelets (a kind of non closed active contour) on the top and bottom of a connected component and by deforming them based on the vertical component of the gradient vector flow. The snakelets are then extended laterally in order to include neighboring connected components. This algorithm has been evaluated on 10 different scripts in[START_REF] Bukhari | Towards generic text-line extraction[END_REF].

  automatically selects the appropriate features based on the desired typewritten text classification accuracy. It selects the first 100 feature vectors of a Principal Component Analysis (PCA) of the character images. Thenany new text is projected into this new space. If it is close enough to the typewritten or the handwritten templates then it is classified appropriately. Otherwise it is considered as made of several touching characters and split with a graph-cut thus making two new connected components to classify. They achieve 98% precision for typewritten text and 71% precision for handwritten text on 500 forms each coming from a different writer. The low handwritten precision is related to the training set that did not contain typewritten text of a small size. As a result small typewritten fonts were classified as handwritten. Replacing the small font size in the test set brings the precisions to 94% and 89% respectively. This highlights the limits of the training set and the versatility of the algorithm with respect to the writing style.Peng et al.[START_REF] Peng | Handwritten text separation from annotated machine printed documents using Markov random fields[END_REF] work at connected component and patch level. Patches are found with a morphological closing. They use a first Markov Random Field (MRF) to classify the patches into typewritten, handwritten or overlapped text. Then, they use another MRF to reclassify them based on their context. The overlapped text is separated at a pixel level with a third MRF and by using Shape Context Features (SCF)[START_REF] Belongie | Shape matching and object recognition using shape contexts[END_REF]. It performs slightly worse than Pinson but the data set size (28 documents) hinders the significance of this performance.

Figure 4 :

 4 Figure 4: Comparison of thresholding and error diffusion binarization techniques. Left: with thresholding, right: with error diffusion.

  Not all algorithms absolutely require a training data set. However, they can have many parameters which may require training. Finally, one should keep in mind that an algorithm that has been trained on a given data set is only supposed to segment correctly similar documents. While it may work for other kinds of documents the training data set is usually a limitation to the segmenting capability of the algorithm. This fact is clearly shown in the scientific papers by the difference of size between the training and testing sets. The training set is often several times larger than the testing set.

  Number of algorithms that studied each language and document type.

Figure 5 :

 5 Figure 5: Venue, language and document type publication trends.

Figure 6a summarizes the

  Figure 6a summarizes the number of publications based on each technique group. The papers are counted in the group in which they were presented above. The techniques in groups 1 and 2 are disappearing to the profit of the third group. The main techniques used for document segmentation are bottom up techniques, in particular geometric clustering and feature classification. They cover 24% and 19% of all surveyed

Figure 6 :

 6 Figure 6: Trends of algorithm techniques and evaluations between 2008 and 2015

Figure 7 :

 7 Figure 7: Breakdown of the number of algorithms based on the number of languages and document types in the evaluation corpus. The radius of each bubble is proportional to the number of algorithms which is also the vertical coordinate. The color of the bubbles relates to the size of the corpus.

Figure 8 :

 8 Figure 8: From top to bottom: evolution of the average number of different languages, the average number of different documents and the average data set size (scale on the right). The dotted lines show the linear tendency of these values.

http://opencatalog.darpa.mil/MADCAT.html

http://www.a2ialab.com/doku.php?id=rimes_database:start

http://www.maurdor-campaign.org/

http://catalog.elra.info/product_info.php?products_id=1242

available at http://www.fki.inf.unibe.ch/databases/iam-historical-document-database

Acknowledgment

This work is financed by the French National Research Agency (ANR) project SHADES referenced under ANR-14-CE28-0022 and by the Town community of La Rochelle.

versity in many data sets prevents us from doing such an analysis. Furthermore, the performance differences of the algorithms between experimental and real data would make such an analysis irrelevant.

Instead, we try to answer two questions related to this: what do they do (functionality) and what do they require to do it (requirements)? Table 1 summarizes this for the 720 main algorithms of this survey. The kind of documents that an algorithm can take as input (layout, multi-layered, color depth, text orientation and alignment) is both a functionality and a requirement. A constraining requirement is the need for training. The output (type of output and labels) produced by the algorithm is a functionality. We ordered them from what seemed to be the most to the least critical from a user/industrial point of view. We added the last three columns (data set size, number of languages and of document types) as a guidance to estimate how extensively the algorithms have been tested and thus how reliable they are.


N Tran

J Berthe

M Brieu

G Portemont
email: gerald.portemont@onera.fr

J Schneider
email: julien.schneider@snecma.fr

Characterization of high strain rate dependancy of 3D CFRP materials

Keywords: composite, interlock, strain rate, experimental, characterization

New composite materials are increasingly used in aviation to reduce the mass of structures. Aeronautic structures have to be designed with respect to a broad range of mechanical loadings during their operational life. These loadings are considered in the design by numerous cases, from low up to high speeds. The motivation of the presented work is to establish and characterize the high strain rate dependency of the linear behavior of composites materials. More specifically, new generations of 3D carbon/epoxy composite materials are of interest because of their high mechanical performances, which require specific experimental developments to be done. Due to the large size of their textile Unit Cell and carbon fiber high strength and stiffness, unusual dynamic test capabilities are required, which leads to revisit the test protocols, specimens definition, instrumentation and exploitation techniques. The experimental method described in this work is applied to analyze the strain rate sensitivity of the mechanical behavior of such a 3D woven composite material. The experiments are done with a servo-hydraulic testing machine (ONERA) in a strain rates range varying between 10 -4 s -1 and 10 s -1 . The linear mechanical behavior of the material in the warp, weft and 45 • orientations is characterized. These tests, together with the new experimental protocol, permit to accurately reveal and measure the material behavior strain rate sensitivity , which proved to be large in the 45 • direction.

Introduction

Currently, different woven composite material configurations exist. Woven architecture can be made in different textile types (taffeta, twill, 3D, 4D, 5D, ...). This study focuses on an epoxy reinforced by layer/layer unbalanced carbon fibers interlock woven developed by SAFRAN Snecma. This Unit Cell, described in Figure 1, as a significant size compared to classic 2D woven composites. The composite volumic warp/weft fibers ratio studied is low unbalanced. A change in warp/weft volumic ratio is made by spacing warp and weft verticaly weaving columns differently. This composite is made of two weaving directions, called warp and weft . Warp yarns weaving with different layers interlocks each layer together. This woven composite particularity prevents the fragile delamination phenomenon to appear. As J. Schneider [START_REF] Schneider | Caractérisation du comportement mécanique endommageable des matériaux composites tissés 3d interlock sous sollicitations quasi-statiques[END_REF] shows in quasi-static tensile tests (ε 10 -4 s -1 ), 3D interlock carbon/epoxy woven composite mechanical behaviour is orthotropic. This woven composite mechanical behaviour presents two domains, firstly a linear one in which the damage is negligible at the macroscopic scale. The second one is a non linear domain due to the development of damage (matrix cracks, fiber yarn cracks, decohesion fiber yarn/matrix).

The in-plane mechanical behaviour of this specific 3D interlock woven composite has been mainly studied under quasistatic or fatigue loadings [START_REF] Schneider | Caractérisation du comportement mécanique endommageable des matériaux composites tissés 3d interlock sous sollicitations quasi-statiques[END_REF][START_REF] Hurmane | Analyse par un dialogue essais/calculs de la tenue en compression de structures composites tissées 3d[END_REF][START_REF] Henry | étude et analyse des mécanismes d'endommagements en fatigue des composites à renfort tissus interlock[END_REF][START_REF] Rakotoarisoa | Prévision de la durée de vie en fatigue des composites à matrice organique tissés interlock[END_REF]. In structure lifecycle, particulary for aeronautic applications, a wide loading speed range could be experimented for many reasons (bird strike, ice strike, ...). It is thus important to study the loading speed influence on materials mechanical behavior in order to design the structure. The present study focuses on the first part of the mechanical behaviour, assumed as linear, in various directions and for different strain rates.

Dynamical testing machine

A servo-hydraulic testing machine was choosen for the dynamical experimentations. This device is particulary used for materials characterization from quasi-static to dynamic loadings up to several 10 m.s -1 .

In order to characterize the 3D woven composite quasi-static behavior, J. Schneider [START_REF] Schneider | Caractérisation du comportement mécanique endommageable des matériaux composites tissés 3d interlock sous sollicitations quasi-statiques[END_REF] proposed specific dog-bone tensile specimen geometry in warp and weft directions. The large size Unit Cell and the high strength and stiffness of the carbon fibers would lead to apply high load levels. The current dynamic experimental device can not reach such load levels. Tensile specimen geometry have to be minimized for dynamic tests. This dimensional change must not impact the intrinsic material properties charaterization.

Dynamic tensile specimen

Rather than performing a costly and time consuming experimental campaign for designing the tensile specimen geometry, a numerical approach has been prefered. The numerical approach is based on numerical Finite Element (FE) tensile test simulations in warp and weft directions, directions in which the load levels are critical. The specimen dimensions influence was studied with respect to the elastic modulus.

Minimization of the tensile specimen geometry

The mesh was realized with a modeling chain tool developed by SAFRAN Snecma [START_REF] Schneider | A meso-fe voxel model of an interlock woven composite[END_REF]. From the reference specimen Zone Of Interest (ZOI) µ-tomography, a textile architectural mesh was made. This specific mesh takes into account possible heterogeneities generated by the manufacturing processes. In this case, carbon fiber yarns are considered elastic orthotropic, and epoxy matrix is considered elastic isotropic.

The ZOI width (W) and length (L) influences on the elastic modulus characterization were studied. The virtual specimens thickness is constant because of the interlocking pattern between each layer in this direction. In each case, displacement boundary conditions representative to a tensile test are applied to the faces orthogonal to the loading direction. The others faces are free in displacement and loading.

Elastic modulus obtained with warp tensile tests for different ZOI dimensions are described in Figure 2(a). Error bars correspond to the dispersion linked to the sample positions. Elastic moduli are normalized by the value obtained with the quasi-static tensile specimen test result (L=1.75 ; W=1). Volume dimensions are normalized by the Unit Cell ones. For W=1 (•), elastic moduli converge quickly to the value obtained with the tested specimen assumed as the converged one. By decreasing the specimen width, W=0.75 ( ) and W=0.5 (•), convergence to the reference solution were observed. A decrease in virtual specimen length by 43% (L = 1) does not significantly alter the elastic modulus identification (error < 1.5%). If the considered ZOI is too small (L=0.25 and W=0.5 as example) the elastic modulus identification varies a lot (± 4.4% different from the mean value). In this case, a significant position sensitivity were noticed.

Elastic modulus obtained with weft tensile tests for different ZOI dimensions are described in Figure 2(b). In this case, virtual tests corresponding to the reference specimen width (W=1) were not studied. Elastic moduli are normalized by the value obtained with the largest virtual specimen (L=1.75 ; W=0.75).

For W=0.75 (•), elastic moduli converge quickly to this reference value. As observed in warp direction, by decreasing the specimen width, for W=0.5 ( ), the convergence to the reference solution were observed. Virtual specimen length decrease by 14% (L = 1.5) does not signicatly alter the elastic modulus, with 1.1% different compared to the current reference value.

In both cases, it was observed that elastic modulus obtained with smaller virtual specimens width and length than the references may be admissible (error < 1.5%). The tensile specimen width reduction limits load levels to apply. In the present study, a 0.75 Unit Cell specimen width in warp and weft directions allows to perform tensile tests with the dynamic servo-hydraulic machine. Dynamic tensile specimen dimensions are summarized in Table 1.

Direction

Experimental validation

Dynamic tensile test specimens, designed by FE simulations, had to be experimentaly validated before characterizing the 3D interlock woven composite mechanical behavior strain rate sensitivity. Quasi-static tensile tests (10 -4 s -1 ) of the dynamic specimens were realized with the servo-hydraulic machine. Longitudinal strain was evaluated by strain gage transversal strain by Digital Image Correlation (DIC). ZOI virtual gage dimension was used to identify the elastic modulus. As defined by the Snecma protocol, warp and weft elastic moduli are obtained by linear regression between 0.1% and 0.4% longitudinal strain. Warp and weft elastic moduli obtained with the dynamic specimens are described in Figure 3(a) and 3(b) (respectively • and •).

Quasi-static tensile tests (10 -4 s -1 ) of the quasi-static specimens proposed by J. Schneider [START_REF] Schneider | Caractérisation du comportement mécanique endommageable des matériaux composites tissés 3d interlock sous sollicitations quasi-statiques[END_REF] were realized with electro-mechanical machine. Warp and weft elastic moduli obtained with the quasi-static tensile specimens are compared to the dynamic ones in Figure 3(a) and 3(b) (respectively and ). The tensile specimen dimensions decrease has no impact on the 3D woven composite elastic modulus characterization. This experimental comparison shows a good correlation with the numerical approach. Tensile tests on the dynamic warp and weft specimens were realized with the servo-hydraulic machine from quasi-static to dynamic strain rates. Tensile tests were made for 3 speeds : 1.7 • 10 -3 m.s -1 , 0.01 m.s -1 and 1 m.s -1 . 3 tensile tests for each speed were carried out to evaluate the dispersion.

Elastic modulus obtained for different speeds in warp direction are described in Figure 4(a) with respect to the mean strain rate, calculated in the elastic modulus measurement gap. Horizontal error bar in Figure 4(a) represents the dispersion in strain rate in the elastic modulus measurement gap. Error bars are not significant for all warp tensile tests. Warp elastic modulus is normalized by the highest one at 10 -4 s -1 . In warp direction, elastic modulus is independent of the strain rate between 10 -4 and 10 s -1 and the dispersion is quite constant.

Poisson' ratio ν 12 obtained in each warp tensile tests is described in Figure 4(b) with respect to the strain rate. Poisson' ratio was evaluated by DIC in the same measurement gap as the elastic modulus. Poisson' ratio ν 12 dispersion is higher than the one of elastic modulus. Low transerval strain levels in the Poisson' ratio measurement gap are close to the measurement uncertainly. Given these low measurement levels, the Poisson' ratio obtained is qualitative. An insensitivity of Poisson' ratio ν 12 relative to the strain rate was observed. In this case, warp mechanical behaviour under ε l < 0.4% of the 3D interlock carbon/epoxy woven composite could be considered linear elastic.

Weft tensile tests

Tensile tests on the dynamic weft specimens were realized with servo-hydraulic machine from quasi-static to dynamic strain rates. 3 tensile tests per speed were ran for 1.7 • 10 -3 m.s -1 , 0.01 m.s -1 and 1 m.s -1 .

Weft elastic moduli, normalized by quasi-static warp elastic modulus, are described in Figure 5(a). As shown in warp case, dispersion in weft elastic modulus is negligeable. Weft elastic modulus strain rate sensivity is not significant between 10 -4 and 10 s -1 . Poisson' ratio also evaluated by DIC allows to make the same observation. In warp and weft directions, 3D interlock carbon/epoxy woven composite mechanical behaviour under ε l < 0.4% can be considered linear elastic. Quasi-static warp and weft 3D interlock carbon/epoxy woven composite tensile specimens require to apply load levels that could not be reached with dynamic servo-hydraulic testing machine. Specific dynamic specimens were then developed in order to adapt the specimens strength to the dynamic testing machine capacity.

Reference tensile specimens geometry are one Unit Cell width. Dimensional and positional sensitivities of the elastic modulus characterization were studied by Finite Element tensile test simulations. In warp and weft cases it was observed that the elastic modulus quantification could be properly performed by reducing the reference width (W) and length (L). Elastic modulus obtained in both cases, with a 0.75 Unit cell width (L=1 in warp direction and L=1.5 in weft direction) is less than 1.5% different from the reference, and relatively independant of the virtual specimen position. A length reduction specimen permits to reach upper strain rate levels than the reference one.

Elastic modulus obtained with the quasi-static and the dynamic tensile specimens at 10 -4 s -1 prove a good correlation with respect to the virtual testing approach.

From specific dynamic warp and weft tensile specimens, quasi-static to dynamic tests were ran in order to characterize the stain rate sensitivity of the 3D interlock carbon/epoxy woven composite linear mechanical behaviour. Elastic modulus and the Poisson' ratio obtained in both cases show a independence to the strain rate between 10 -4 and 10 s -1 .

In conclusion, warp and weft mechanical behaviour under ε l < 0.4% of the 3D interlock carbon/epoxy woven composite can be considered linear elastic.

Fig. 1 .

 1 Fig. 1. Representation of a complex 3D interlock woven fabric composite Unit Cell

Fig. 2 .

 2 Fig. 2. Evolution of the normalized warp elastic modulus with the size and position of the specimen

Fig. 3 .

 3 Fig. 3. Comparison of elastic moduli obtained with the reference specimens and the dynamic ones

Fig. 4 .

 4 Fig. 4. Dynamic warp tensile

Fig. 5 .

 5 Fig. 5. Dynamic weft tensile tests

Table 1 .

 1 Length of the ZOI (L) Width of the ZOI (W) ZOI dimensions of the warp and weft dynamic tensile specimens

	Warp	1.4 Unit Cells	0.75 Unit Cell
	Weft	2.3 Unit Cells	0.75 Unit Cell

Acknowledgements

This research was supported by SAFRAN Snecma. We thank our collegues from SAFRAN (Y.WIELHORSKI, T.FIXY, ...), ONERA (M.RAGONET, A.DEDON, ...), Centrale Lille and LML who provided expertise and technical support that greatly assisted the research.

We thank E.Deletombe (ONERA) for assistance with particular scientific methodology and for comments that greatly improved the manuscript.