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

Petra Gomez-Krämer

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

When document security brings new challenges to document analysis

Keywords: Hybrid security, Text hashing, OCR hashing, Document analysis robustness

It is very easy to ensure the authenticity of a digital document or of a paper document. However this security is seriously weakened when this document crosses the border between the material and the digital world. This paper presents the beginning of our work towards the creation of a document signature that would solve this security issue. Our primary finding is that current state of the art document analysis algorithms need to be re-evaluated under the criterion of robustness as we have done for OCR processing.

Introduction

With the ever increasing digitization of our world, people and companies now have to ensure the authenticity of many documents. For instance, an easy way to get a fraudulent identity card is not to forge one but to obtain a real one with fraudulent documents such as a fake electricity bill and a fake birth certificate [START_REF] Smith | Identity fraud: a study[END_REF]. Some of these documents are in a paper format and some are in a digital format. Ensuring the security of these two kinds of documents and of documents that can change format is called hybrid security. So far there is no other choice but to use two authentication systems: one for the paper documents and one for the digital documents. Even though watermarks or fingerprints can bridge the gap between the paper and the digital world they do not ensure the authenticity of the content of the document. They only ensure the authenticity of its support i.e. the file or the paper material [START_REF] Baras | Vers un modèle de canal réaliste pour l'analyse de la sécurité du processus d'authentification par code matriciel 2D[END_REF].

The digital world has a very efficient tool to ensure the authenticity of a file: a hash key [START_REF] Zauner | Implementation and benchmarking of perceptual image hash functions[END_REF]. It cannot be used as-is on a paper document because of the noise of the scanning process which would always produce different files. We have the idea of extracting the content of the document and to hash this content instead of the raw scan of the document. This raises the immediate question of the content we want to extract. Is it just the text or does it also include the images, the handwritten signatures, or even a combination of those? And with which precision do we want to extract it? Is it plain text or do we also want to have the font, the font size and the emphasis? While investigating this question, our first experiments prove that most document analysis tasks need to be thought again under a completely new paradigm in this community: robustness. It appears that current content extraction algorithms produce very different results with only a slight amount of noise. This makes it impossible to produce a reproducible signature. We started studying this robustness with the base algorithm of our signature: OCR. We plan to study the other necessary algorithms after we obtained a suitable OCR.

This paper is organized as follows. In Section 2, we introduce the general problem of hybrid signature and the performance objectives. Section 3 presents the workflow we intend to build to solve it and the issue of robustness. Then, we present our analysis for the task of OCR analysis in Section 4. Finally, Section 5 concludes our work.

Hybrid Signature

Before presenting the hybrid signature itself we will present the hash algorithms on which it is based.

Digital Hash Algorithms

A digital hash algorithm computes a digest for a message. A very good overview of digital hash algorithms can be found in [START_REF] Zauner | Implementation and benchmarking of perceptual image hash functions[END_REF].

The first kind of hash algorithm was cryptographic hashing. It was made in order to be able to control the integrity of the message content without having to read the entirety of the message. This was useful at the beginning of the Internet because of network transmission errors. Cryptographic hash algorithms are now mostly used for security applications and content retrieval. They have several features. The first one is that any small change in the message will change the digest with a very high probability. This is reflected in the collision probability, which is the probability of two different messages having the same digest. Another important feature of hash algorithms is the inability to recover the original message from its digest (hence the name "cryptographic"). The main consequence of this requirement is that any smallest change will completely change the digest. This allows the authentication of a confidential message without having to compromise the confidentiality of the message. The current standard cryptographic hash algorithm is SHA-256 as defined in the Federal Information Processing Standard FIPS PUB 180-4 [START_REF] Bryson | Secure Hash Standard[END_REF] and FIPS PUB 186-4 [START_REF] Kerry | Digital Signature Standard (DSS)[END_REF]. A security analysis of SHA-256 can be found in [START_REF] Gilbert | Security analysis of SHA-256 and sisters[END_REF].

The next kind of digital algorithm is fuzzy hash algorithms. Contrarily to cryptographic hashes, a small change in the message will only change a portion of the digest. This allows the retrieval of different messages that have similar message parts, but that are not completely identical (hence the name "fuzzy"). For this reason, the content of the message is not as protected as in a cryptographic hash algorithm. The most common fuzzy hash algorithm is ssdeep [START_REF] Kornblum | Identifying almost identical files using context triggered piecewise hashing[END_REF]. Fuzzy hash algorithms are also called perceptual hash algorithms especially in the image processing community as the fuzzy hash is related to the content of the message and to the way a human perceives it. They are widely used for message retrieval, where the message can be of any kind such as an image [START_REF] Hadmi | Perceptual image hashing[END_REF], a text [START_REF] Belazzougui | Improved compressed indexes for full-text document retrieval[END_REF] or even raw bits of data on a hard drive [START_REF] Winter | F2S2: Fast forensic similarity search through indexing piecewise hash signatures[END_REF]. A security analysis of perceptual hash algorithms can be found in [START_REF] Koval | Security analysis of robust perceptual hashing[END_REF].

Figure 1 shows the differences between these different hash algorithms and the proposed one.

Hybrid Security Algorithms

Villán et al. [START_REF] Villán | Tamperproofing of electronic and printed text documents via robust hashing and datahiding[END_REF] elaborated two hashing algorithms. The first one is based on the combination of an OCR software (Abbyy Finereader) and a cryptographic hash (SHA-180). The second one is based on a random tiling hash, which computes the average luminance value on 1024 random rectangles for each word. They used an Arial font with a font size of 10 and no emphasis. The text was simple English text. While the first algorithm performs rather well with only two errors out of 64, the random tiling algorithm cannot differentiate one character from a similar one such as "o" and "e".

Tan et al. [START_REF] Tan | Perceptual text image hashing based on shape recognition[END_REF] developed a perceptual text hasing algorithm, which is very interesting as it is based on the skeleton features of each character. It has the drawback of removing all punctuation from the text.

The most recent work on hybrid security was made in two projects: the ANR Estampille [START_REF] Baras | 2D bar-codes for authentication: a security approach[END_REF] [2] and the European project SIGNED [START_REF] Garcià | Secure Imprint Generated for Paper Documents (SIGNED)[END_REF].

The Estampille project aimed at developing a 2D-barcode that could be used as a fingerprint. The barcode is printed with extreme precision in a specific printing process. This fingerprint is supposed to be impossible to be reproduced or to be copied without detection. The latest results actually prove that having a dozen copies of an authentic fingerprint is enough to forge one. This does not include the fact that the document content is not included in the fingerprint. Thus once a forged fingerprint is made, it is possible to render any document authentic-like.

The SIGNED project was more ambitious and corresponds to what we can call a "hybrid signature". The goal of the project was to produce a digest of a document that allows the detection of any modification. It is based on a fuzzy hash algorithm, which has the disadvantage of breaching the possible confidentiality of the document, but this also allows for the localization of the modification. The document is analyzed at the signal level. They cut the document in tiles and use a Discrete Haar Wavelet Transform [START_REF] Haar | On the theory of orthogonal function systems[END_REF] on each of these tiles. For a document scanned at 600dpi, the tiles have a size of 64 by 64 pixels. Then a cryptographic hash is applied on each tile and all the digests are concatenated to create a fuzzy digest. The fuzzy digest is then printed on the document. During the verification process the digest of the scan is computed and compared with the one that is printed on it. A distance is computed between these two digests and if it is too large the document is considered to be fraudulent.

The results of the SIGNED project had to meet six performance indicators:

1. Probability of missed detection and false alarm (a) Probability of false alarm (PFA) below 0.001 (b) Probability of missed detection (PMD) below 0.001 with P F A < 0.001 for the replacement of digits in Arial 8, 10 and 12 for the replacement of dots by commas in Arial 10 and 12 2. Collision probability below 0.001 3. Minimum area size to detect a manipulation: 42 × 42 pixels at 600dpi 4. Throughput below 5 seconds per page 5. Size of the document digest below 4 kB 6. Compatibility with current scanners and printers A false alarm occurs when a document is detected as fraudulent while it is not and a missed detection is the contrary. The minimum area size means that a manipulation has to be bigger than a square of 42 by 42 pixels to be detected.

The project met all these requirements except for:

-The PMD for the replacement of dots by commas that required a bigger font than Arial such as Verdana -The minimum area size that is of 64 × 64 pixels at 600dpi -The throughput that was not achieved for the verification phase (no figure was given) -The size of the document digest that was between 4.8 and 170 kB depending on the required precision

The performance indicators were given by the industrial partners of the project and as such represent a reasonable goal to reach. We can also notice that if we want to use OCR processing the minimum area size performance indicator is not relevant anymore.

Proposed Solution

Since a hash algorithm cannot be applied directly on a document image because of the variability and the acquisition noise, our idea is to extract the content from the document image, to format this content properly and to apply the hash algorithm on it. This will drastically reduce the amount of data to hash and will allow to hash only the significant (semantic) content of the image. The interest of extracting the content is that this is exactly what is not supposed to -and what we do not want to -change. This will eliminate the noise and so the variability of the data, and will allow the use of a cryptographic hash. Thus, we can expect this technique to be applicable also in the case of a camera captured document.

As the notion of "semantic" can have several meanings we will attempt to define it now. Usually a hash algorithm is applied directly on the raw data, the bits of information. We intend to apply it on the content extracted from the raw data. Hence we consider a semantic hash on the contrary to a normal hash. We do not take into account the level of abstraction of the content on which we apply the hash. For instance, applying a hash algorithm on a sequence of characters without any understanding of their division in words still makes a semantic hash. What matters is that the data on which is the hash algorithm applied to is the one that contains only the information that is meaningful for a human (and in our case that is not supposed to change).

Signature Workflow

Figure 2 shows the basic workflow for the signature computation. There are three main phases: the preliminary phase (orange) extracts the different elements such as text, images, tables and diagrams from the document image. The second phase (gray) extracts the content of each of these elements. The last phase (green) reconstructs the document and computes its digest.

The first step of the preliminary phase removes any geometric distortions such as skew and warp. We then proceed with the segmentation phase and the tagging of each segmented element according to its content (text, image, table, etc.).

During the second phase, the elements are analyzed by a content extraction algorithm. The algorithm is specific for each element tag such as an OCR for the text.

Finally all the extracted contents are used to rebuild the document according to the segmented and analyzed data. We apply SHA-256 to compute the document hash.

The Issue of Robustness

The objectives require a false positive rate below one in a thousand and the same for a missed detection. The case of missed detection is not very important, except for some specific cases. For instance, in the case of undersegmentation, missed detections are mainly related to the precision of each content extraction algorithm. Should one algorithm not be good enough, we can either try to improve it, not use it and consider that the corresponding information is not secured or consider that the corresponding information is secured with a degraded level of security. Another solution is to only consider certain types of document images for which we have the desired accuracy. The precision of most document analysis algorithms is the most frequent criteria used to evaluate them. So the precision is usually quite good.

The case of false positives is very different. To prevent a false positive, we need to ensure that an algorithm will produce the same results for reasonably similar images of the same document and/or with some additional noise. This is the robustness of the algorithm and it is usually not analyzed. The issue with robustness goes even further than that: with a missed detection we accept a document that has a necessarily small modification (otherwise we would not miss it), while with a false positive we reject an entire document that is completely fine. From a practical point of view, if the rate of false positives is too high, there will be too many rejected documents. This means that either the document verification process is useless or it will require a lot of manpower to hand-verify each rejected document. False positives can be created at every step of the signature process: the segmentation, the content extraction and the document reconstruction can all produce false positives that will have a direct impact on the signature.

This shows how critical it is to ensure the robustness of the algorithms used to compute the document signature. Unfortunately this robustness has hardly been studied. We did this work for OCR and present it in the next section.

Study of OCR Capabilities

We will first describe in detail our test dataset, our test protocol and our results of the OCR analysis. Finally we will discuss possible OCR improvements.

Dataset

Considering the quite stringent requirement for the OCR accuracy, we chose to use clean, text-only, typewritten documents. Tesseract can analyze documents with a single or double column layout, so we tested it with a combination of these. We used only and all the characters that it can recognize.

The dataset is made of 22 pages of text with the following characteristics:

-1 page of a scientific article with a single column header and a double column body -3 pages of scientific articles with a double column layout -2 pages of programming code with a single column layout -4 pages of a novel with a single column layout -2 pages of legal texts with a single column layout -4 pages of invoices with a single column layout -4 pages of payslips with a single column layout -2 pages of birth extract with a single column layout We created several variants of these 22 text pages by combining:

-6 fonts : Arial, Calibri, Courier, Times New Roman, Trebuchet and Verdana -3 font sizes : 8, 10 and 12 points -4 emphases : normal, bold, italic and the combination of bold and italic This makes 1584 documents. We printed these documents with three printers (a Konica Minolta Bizhub 223, a Sharp MX M904 and a Sharp MX M850) and scanned them with three scanners and at different resolutions between 150dpi and 600dpi as shown in Table 1. This makes a dataset of 28512 document images. Figure 3 shows an example of the images contained in the dataset.

Test Protocol

Most of the security algorithms are publicly available. For this reason we chose to use Tesseract [17] which is open-source. We used Tesseract version 3.02 with the default English training. We ran it on every image of the data set and used the ISRI evaluation tool [START_REF] Rice | The fifth annual test of OCR accuracy[END_REF] to compute the accuracy of the OCR and to analyze its errors. We also computed a hash digest of each OCR output file with SHA-256. We used these digests to compute the probability of false positives.

Scanner 150dpi 300dpi 600dpi Konica Minolta Bizhub 223

X X Fujitsu fi-6800 X X Konica Minolta Bizhub C364e X X Table 1. Scanning resolution for each scanner Fig. 3. An example of three document images of the dataset Computation of PFA We will explain in the following the computation method for the probability of false positives. We consider a set of n documents. What a document exactly is will be defined for each computation. For each document there are

m i different digests, i ∈ [1, n]. Each digest is present s ij times, j ∈ [1, m i ]
. This creates a pseudo matrix S ij containing all the s ij values. For any i, m i is the number of non null values on the i th row and the number of images is the sum of all the values contained in the matrix.

The signature verification process can be modeled by the successive draw without replacement of two digests among all the digests available for the document. The draw is without replacement as we consider it impossible to produce twice exactly the same image. A false positive happens when the two digests that are drawn are not the same. Hence the probability of a false positive for the i th document is given by:

P i = 1 - mi ∑ j=1 ( s ij ∑ mi k=1 s ij × s ij -1 ∑ mi k=1 s ij -1 ) . ( 1
)
The global false positive probability is the mean of the probabilities for each document.

Post Processing After some preliminary tests we noticed that it is unreasonable to require the OCR to distinguish some characters such as a capital "i" and a lower case "l" or a capital "o" and a zero. Tesseract regularily mistakes on for the other and it would be the same for a human. For this reason we added an alphabet reduction as post processing step.

Results

We evaluate the results of our proposed method in terms of precision, probability of false positives and collision probability, which are detailed in the following. Table 3 sums up most of our results.

Precision

The OCR precision ranges from 14.5% to 100% with an average of 98.08%. The worst results are obtained for the pages of code as tesseract does not handle well the code text syntax. The other low precision results are due to segmentation errors.

The precision increases seriously when using a resolution of 300dpi rather than 150dpi as it increases from 91.58% to 99.33%. The improvement is much less significant when using 600dpi instead of 300dpi with a precision reaching 99.45%.

The font size and emphasis also play an important role. The average precision is 95.83%, 99.02% and 99.38% respectively for a font size of 8, 10 and 12 points. The use of italic worsens the accuracy results as, by instance, the vertical bars "|" can be misrecognized as division bars "/".

The choice of the font has a similar effect. Courier and Times New Roman get the worst results and the best ones are obtained for Verdana. This is explained by the fact that Courier characters have a very special shape, Times New Roman is the smallest font and Verdana the biggest.

Even though the accuracy results are not perfect they allow for us to meet the probability of missed detection criteria.

False Positives

The probability of false positives is quite different. As the OCR extracts only the text without taking into account the font, font size or emphasis we can consider that our dataset as 1296 copies of 22 document pages. A document is then only defined by its textual content. This produces a probability of false positives of 92%!!

We then decided to consider a document as being defined by its textual content, the font, font size, font emphasis and scanning resolution. Our dataset is then composed of between 3 and 9 copies of 4752 documents. This produces a probability of false positives of 84%. This is where increasing the scanning resolution has a real interest as the probability of false positives decreases from 99% to 79% and to 73% for a resolution of 150, 300 and 600dpi respectively. The other influencing factors are the same as for the probability. This is understandable as the less errors there are, the less variation possibilities there are and the lower the false positive probability. However one could imagine that the same errors could be done every time thus reducing the false positive probability. This is not the case.

The best case scenario is when we consider a scanning resolution of 600dpi, a font size of 10 or 12 points, no italic emphasis and any font but Courier and Times New Roman. This allows us to reach a probability of false positives of 57% and even 53%, if we do not take into account the pages of code. The OCR precision reaches 99.79% and 99.83% in these two cases respectively.

We can see that the issue of robustness has not been resolved at all. If we consider a text of 2000 characters and we want to have less than one different OCR text out of one thousand copies of the text; this means an error rate of one in two million.

Collision Probability

The collision probability is the probability of having two different documents producing the same digest. It can be due to three factors: the OCR, the alphabet reduction and the hashing algorithm.

The OCR introduces a collision probability when it recognize two different characters as the same. This probability can be considered equal to its error rate which is about 0.002.

The alphabet reduction introduces a collision when two different characters are replaced by the same character. However the alphabet reduction was made so that only characters that a human could mistake for one another are replaced. This means that it does not actually create collisions except for reference numbers combining letters and numbers and for the replacement of capital "i" by an "l". We applied the alphabet reduction algorithm on the Aspell English dictionnary in order to see how many similar words it would produce. As expected the only collisions were due to the replacement of a capital "i" by an "l". If we take the font case into account we obtain a collision probability of 0.0002.

Finally SHA-256 has a negligible collision probability usually below tens of orders of magnitude below the OCR and alphabet reduction collision probabilities. No collision has been found so far for SHA-256 [START_REF] Gilbert | Security analysis of SHA-256 and sisters[END_REF].

Hence, the most critical part is the OCR precision which brings the collision probability up to 0.002. It should not require much work to bring it below 0.001. Other Performance Criteria All the other performance criteria are met. The probabilities of missed detections are equal to the OCR error rate, which is below 0.1% in the case of digits, commas, and dots. The minimum area size is not relevant for an OCR algorithm. The throughput is about 2 seconds on average which is well below 5 seconds. SHA-256 produces a digest whose size is 256 bits, which is well below the 4kB limit. Finally, our system was tested with three printers and three scanners which proves its compatibility with current scanners and printers.

Criteria

Possible Improvements

Kae et al. [START_REF] Kae | Improving state-of-the-art OCR through high-precision document specific modeling[END_REF] created a document specific OCR for each document. They ran Tesseract on the document to detect a set of reliable characters. Then they used SIFT as a character descriptor and an SVM classifier to OCRize the document. Unfortunately this requires training the classifier for each document and prevents the algorithm from performing in real time, which is necessary for our application. They used a test set of 10 documents and reduced Tesseract's error rate by 20%.

Reynaert [START_REF] Reynaert | Non-interactive OCR post-correction for giga-scale digitization projects[END_REF][21] created a lexicon of word variants to compensate for OCR errors. He applied a space reduction similar to our alphabet reduction and searched for the word in the lexicon in order to find its correct form. This allows for the correction of any errors within a Levenstein distance of 2 e.g. a maximum of two edition operations. The algorithm called TICCL can detect between 55% and 89% of OCR errors on a corpus of Dutch newspapers.

Finally, Niklas [START_REF] Niklas | Unsupervised post-correction of OCR Errors[END_REF] combines the work of Reynaert with a new word hashing algorithm called OCR-Key. He achieves an error reduction rate between 39% and 75% on a corpus made of several issues of The Times newspaper between 1835 and 1985. However for these last two works, the use of a lexicon is inapplicable for names or reference numbers combining letters and numbers especially those occurring in invoices, playslips etc.

We also started preliminary testing with Abbyy Finereader which is considered to be more robust than Tesseract by the document analysis community. We expect an improvement between one and two orders of magnitude for the error rate.

Conclusion

We presented our beginning work on securing a hybrid document by creating a document signature based on its content. The issue of robustness is the most critical and needs to be studied for every task involved in the computation of the document signature. This could also be a criteria not to include some document features in the signature. If the extraction algorithm for a document feature is not robust enough, the probability of false positives will be too high and hence should not be included until it has been improved.

We found that the robustness of Tesseract is quite low. While an accuray of 99.83% is quite good; a probability of false positives of 53% is not acceptable. The objective is to have it below 0.1%. Moreover, these figures are obtained in a constrained best case scenario. The scanning resolution has to be at least 600dpi and the font size no less than 10 points. There can be no italic emphasis and no small fonts such as Courier or Times New Roman. The content of the document must also respect some sort of human readability e.g. it cannot be programming code. Another finding is that increasing the scanning resolution from 300dpi to 600dpi does not improve the accuracy much but it significantly reduces the probability of false positives. The collision probability at 0.002 is nearly acceptable and the other performance criteria are satisfied.

One can also wonder about the robustness of segmentation algorithms and of the retranscription of the document structure. Any quantization or randomness will most likely lead to a fragile and/or not reproducible algorithm.

We have shown that the current state of the art does not perform sufficiently well on a seemingly easy task when studied under the angle of robustness. This issue of robustness is of great interest as it could lead to a new document security technology. Considering the work at hand any help or collaboration from the document analysis and security community would be welcome.

Fig. 1 .

 1 Fig. 1. Comparison of proposed, cryptographic and fuzzy digests on several copies of the same document and a fraudulent version of it. The cryptographic digests have nothing in common while the fuzzy ones all contain small variations making it impossible to identify which document is fraudulent.

Fig. 2 .

 2 Fig. 2. The workflow of the signature computation.

Table 2 .

 2 Table 2 summarizes the alphabet reduction. Alphabet reduction

	Character

Table 3 .

 3 Average values of the results of the OCR testing

			General case		Best case scenario
		150dpi 300dpi 600dpi All resolutions
	Precision	91.58% 99.33% 99.45%	98.08%	99.83%
	Probability of false positive 99%	79%	73%	84%	53%
	Collision probability	0.0084 0.007 0.004	0.019	0.002


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

Petra Gomez
email: petra.gomez@univ-lr.fr

-Krämer -Jean-Marc Ogier

The Delaunay document layout descriptor

Keywords: layout, descriptor, Delaunay, stability, hashing, retrieval, classification

Security applications related to document authentication require an exact match between an authentic copy and the original of a document. This implies that the documents analysis algorithms that are used to compare two documents (original and copy) should provide the same output. This kind of algorithm includes the computation of layout descriptors, as the layout of a document is a part of its semantic content. To this end, this paper presents a new layout descriptor that significantly improves the state of the art. The basic of this descriptor is the use of a Delaunay triangulation of the centroids of the document regions. This triangulation is seen as a graph and the adjacency matrix of the graph forms the descriptor. While most layout descriptors have a stability of 0% with regard to an exact match, our descriptor has a stability of 74% which can be brought up to 100% with the use of an appropriate matching algorithm. It also achieves 100% accuracy and retrieval in a document retrieval scheme on a database of 960 document images. Furthermore, this descriptor is extremely efficient as it performs a search in constant time with respect to the size of the document database and it reduces the size of the index of the database by a factor 400.

INTRODUCTION

Many documents need to be secured, ideally by the means of an electronic signature. If two documents have the same signature, then they are authentic copies of each other and if their signatures are different, one of the two documents is fraudulent or at least different from the other one. This concept works well for naturally born digital documents. However, nowadays a document, the so-called hybrid document, is often used in electronic or paper form according to the need. Hence, the hybrid document undergoes a lifecycle of printing and scanning and thus different degraded versions of the document exist as the printing and scanning process introduces specific degradations in the document such as print and scan noise [START_REF] Kanungo | Global and local document degradation models[END_REF]. Thus, the concept of electronic signature can not be applied. For this reason, our work intends to develop an advanced electronic signature for the field of securing hybrid documents, the so-called hybrid security. Our idea is to extract the layout, the text and the images from the document to compute a stable signature that will be the same for all the authentic copies of the document.

To our knowledge, the closest work is a signature [START_REF] Garcià | Secure Imprint Generated for Paper Documents (SIGNED)[END_REF] based on pixelwise signal analysis techniques which is not satisfactory because of its large size. Other signatures such as the 2D-Doc [START_REF]Spécifications techniques des Codes à Barres 2D-Doc[END_REF] require the emitter of the document to precise the information used for signature computation, e.g. the name and the address of the beneficiary in the context of an invoice, and thus secures only partially the document (the provided information, but for instance not the layout). Thus, an ideal signature computation process is to automatically extract the content of the document (text, layout, graphics) and use it in the signature computation. A smaller signature than [START_REF] Garcià | Secure Imprint Generated for Paper Documents (SIGNED)[END_REF] will result as the amount of information to be secured is smaller since the image is not processed pixelwise. Anyhow, this signature will still allow to secure the whole information of the document. In consequence, this requires document analysis techniques with an extreme stability especially with regards to print and scan noise. The first step in a document analysis process is often the segmentation of the document. Hence we need to evaluate the stability of a segmentation algorithm.

Before going any further it is important to understand the difference between accuracy and stability. Accuracy requires a groundtruth to evaluate how close a result is to this ground truth. Accuracy can be evaluated with only one result as long as there is also a ground truth. Stability does not require a ground truth. Stability requires at least two results with similar inputs to see how close these results are together compared to how close the inputs were. In our case, similar inputs are photocopies of the same document. A consequence of this is that an algorithm can be very stable and yet not be accurate, For instance an algorithm that always makes the same mistakes, or namely in the case of a layout descriptor always describes only one region, would have an absolute stability and zero accuracy. The contrary is not true. An algorithm with an absolute accuracy will always produce results that are identical to the ground truth and hence identical between each other. A perfect layout descriptor will also be perfectly stable.

Hence we do not need a ground truth to evaluate the stability of a segmentation algorithm but we still need a proper metric or criteria to know when to outputs are similar or not. This also raises the question of defining what are similar outputs of a segmentation algorithm. Our point of view is that two segmentation results are similar if they contain the same layout. This layout is also part of the semantic content of the document that will need to be secured.

Since we make a difference between the segmentation and the layout of a document, it is necessary to define it clearly. According to [START_REF] Chaudhuri | Digital document processing. major directions and recent advances[END_REF], the physical layout of a document refers to the physical location and boundaries of various regions in the document image. The physical layout extraction typically relies on a page segmentation algorithm. The page segmentation computes the boundaries of the various regions in the document image. Then, based on these boundaries, the layout extraction determines the spatial relationships between these regions. We simplify the above definition by only keeping the physical locations of the regions for the layout. We consider that the position of the region boundaries is the page segmentation. The region boundaries of page segmentation vary in case of noise and are thus very unstable. Hence, we consider that the three segmentation results shown in Figure 1 have different segmentation results but identical layouts. This is of course a point of view which is not unique but it allows us to achieve the required level of stability.

Figure 1: Three layouts that we consider to be identical Now we need a layout descriptor that is at least as stable as the best segmentation algorithms. We can never measure anything more stable than the descriptor, hence our quest for stability. The Delaunay Layout Descriptor is made to identify layouts with the highest level of stability. While its original use is the evaluation of segmentation algorithms, its performances allow many other uses.

It has been designed for document authentication. Assuming we have a copy of a layout and the descriptor of the original layout, the authentication process is as follows. First we compute the layout descriptor on the copy. Then we match it with the descriptor of the original layout.

It can also be used for document retrieval based on the document layout with unprecedented results. For a document retrieval scheme, we would have one layout and a database of hashes of layout descriptors. We would retrieve the layout by matching its descriptor with the database.

More generally, this descriptor can be efficiently used to describe the relative spatial relationship between a set of points as long as these points are not too numerous (below 30-40) and not too many of them are aligned.

We will now consider the state of the art under this new perspective in section 2. Then we will present the computation and the matching algorithm for the Delaunay Layout Descriptor (DLD) in sections 3 and 4. Section 5 presents the metrics and the dataset used for the evaluation of the descriptor. Finally, the last three sections 6, 7 and 8 detail our results, discuss the pertinence of our descriptor and conclude.

STATE OF THE ART

As far as we know, only a few work has been presented on layout descriptors. For instance, the Description and MOdification of Segmentation DMOS with the EPF grammatical language [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] can be used to provide an original layout description. It extracts content from a document by identifying its layout. The DMOS paradigm requires the user to a priori define the layout with EPF and is not based on the content of the document image to be processed. Hence the layout description is not adaptive to the layout of the document at hand.

Álvaro and Zanibbi [START_REF] Álvaro | A shape-based layout descriptor for classifying spatial relationships in handwritten math[END_REF] propose a layout descriptor for handwritten math expressions. They use a polar histogram and a support vector machine to classify the spatial relationship between two elements. There are five classes: horizontal, superscript, subscript, below, and inside (e.g. in a square root).

The other layout descriptors are made for document classification and retrieval. The MPEG-7 standard [START_REF] Kasutani | The MPEG-7 color layout descriptor: a compact image feature description for high-speed image/video segment retrieval[END_REF] includes a color layout descriptor. It divides an image into an 8 by 8 grid, takes the mean color value of the grid, converts it into the YCbCr color space and runs a discrete cosine tranform on it. Esposito et al. [START_REF] Esposito | Multistrategy learning for document recognition[END_REF] use a set of 7 quantized position and size attributes (e.g. width, height, on top of) whose values can make 171072 combinations. Cesarini et al. [START_REF] Cesarini | Encoding of modified X-Y trees for document classification[END_REF] modify the X-Y cut algorithm and use the cut sequence to encode the layout. This descriptor is tied to the segmentation algorithm and hence not very useful in a general case. There are also many graph-based layout descriptors [START_REF] Bagdanov | First order Gaussian graphs for efficient structure classification[END_REF][START_REF] Gordo | A rotation invariant page layout descriptor for document classification and retrieval[END_REF][START_REF] Liang | Page classification through logical labelling[END_REF] using features such as distance, size, position, angles and other metrics.

While the above presented descriptors do not consider robustness to noise, rotation and scale, Gordo and Valveny [START_REF] Gordo | A rotation invariant page layout descriptor for document classification and retrieval[END_REF] present one which is meant to be invariant to scale and rotation. Unfortunately, by 'invariant' the authors mean reasonably invariant. For instance, if we consider two copies of the same document, a small difference is accepted as long as the descriptors of the copies can be matched. This 'weak' invariance is not enough for security application which require an exact invariance, e.g. the values of the descriptor should remain the same.

There is one last descriptor that is not made for layout analysis but which presents some interesting features: LLAH [START_REF] Nakai | Use of affine invariants in locally likely arrangement hashing for camera-based document image retrieval[END_REF]. Nakai et al. designed it to retrieve text documents in a database with an image captured by a camera. It describes the local layout around each word in the document. It uses a set of affine invariants computed at the center of each word in the document. The descriptors reflect the spatial relationships between a word and its neighbors making a word neighborhood descriptor. Each word neighborhood descriptor is stored in a database with a hashing technique. This technique allows constant time retrieval which in practice leads to real time retrieval. The matching is made with a voting algorithm counting how many word neighborhoods of the document can be matched in the database. It cannot be used for layout description because it requires more centroids than the number of regions that we would find in a common document. Also it only retrieves one document per query and cannot cluster identical documents.

The main drawback of state-of-the art layout descriptors is the number of thresholds and parameters to adjust. The more thresholds and parameters are used in the computation, the more unstable the descriptor will be. Thus, the ideal stable descriptor neither uses thresholds nor parameters.

THE DELAUNAY LAYOUT DESCRIPTOR

Considering our last comment, one should ban the use of "continuous" values such as distances or areas. If a length can vary between 1 and 100; then it has 99 thresholds. An interesting descriptor without any threshold would be a graph joining the centroids of the regions of the layout. One way to compute such a graph is to use the Delaunay triangulation of the centroids. There are three properties of a Delaunay triangulation that influence its practical use and stability.

Property 1. Given a set of points, there always exists a Delaunay triangulation except when all the points are aligned.

This property is of the highest interest as it proves that we will always be able to compute a Delaunay triangulation. Yet, it also highlights one case of instability: aligned points. While this will never occur for the whole page, it can occur locally and create local instabilities.

Property 2. The Delaunay triangulation tries to maximize the minimum value of the angles inside each triangle.

This leads to only few near flat triangles whose degenerated form could lead to an instability.

Property 3. When a subset of four or more points can be placed on the same circle, the Delaunay triangulation of the points is not unique.

This means that in this case, the Delaunay triangulation is not stable. This is why, our descriptor is based on the Delaunay triangulation of the centroids of the regions of the layout. This triangulation is represented as a graph whose root node is the top left centroid. From there we use a breadth first traversing algorithm to order the graph and to compute its adjacency matrix. The adjacency matrix is the descriptor which we call the Delaunay Layout Descriptor (DLD). It has no parameter and virtually no threshold.

The computation of the Delaunay Layout Descriptor is based on a preliminary step: we extract the centroids of the regions of the layout. Two steps follow: the triangulation of these centroids and the computation of the adjacency matrix of the triangulation which is seen as a graph.

Delaunay triangulation of the centroids

The algorithm adds three points outside of the document image in order to compute the triangulation. One is far in the top left direction and will be the root of the graph. These points are the furthest points from the center of Figure 2.

The pseudo code algorithm of the triangulation is:

Delaunay ( vertices set V ) vertex list Tv triangle list Tt create 3 outer vertices v1 , v2 , v3 The update method updates the removed triangles to include the new vertex a (the last vertex in Tv). This is done by adding the vertex a to these triangles. This makes quadrangles that are split along one diagonal to make new triangles that will be added to Tt. The condition to choose along which diagonal to split the quadrangle is detailed in the next section.

Graph transformation of the Delaunay triangulation

The Delaunay triangulation can easily be seen as a graph but this graph needs to be ordered in a stable manner. To this intend we use a variant of the breadth-first search (BFS) algorithm starting from the top left corner. Our algorithm is described below in pseudo-code. Once the graph is ordered we compute its adjacency matrix to obtain the DLD. The DLD can be hashed with any hashing algorithm such as MD5 [START_REF] Rivest | The MD5 message-digest algorithm[END_REF] or SHA-256 [START_REF] Bryson | Secure Hash Standard[END_REF] in order to reduce its size to 128 or 256 bits respectively. MD5 is more compact than SHA-256 but cannot be used for secure applications. It should only be used in a document classification and retrieval scheme.

DLD MATCHING

We have created a descriptor with no threshold or parameter. However this is not sufficient for an absolute stability. We have seen that there are three cases of instability: aligned points, flat triangles and cocyclic points. Flat triangles and aligned points cover the same geometric situation. There is also a fourth one related to the ordering of the graph. Thus, we propose an appropriate matching algorithm absorbing these possible sources of unstability of the descriptor. It creates the possible variations of the descriptor and finds the exact matches with the descriptor(s) that we want to match. The way the matching algorithm handles the flipping of edges inside a quadrangle, the instability due to near aligned points and the instability due to the implicit threshold at -π/π in the ordering of the graph is explained in the following.

Edge flipping

The Property 2 can be achieved by appropriately choosing the diagonal to split the quadrangles in the update function of the triangulation algorithm. If we consider the quadrangle ABCD of Figure 4, it can be split along [AC] or along [BD] to make two triangles. To choose which edge must be created, the algorithm computes the sum of the opposing angles: ABC + CDA and BCD + DAB. One of them is bigger than 180 • (this is a trivial mathematical property since their sum is equal to 360 • ). To statisfy P2, the quadrangle must be split along the segment that joins the opposing angles whose sum is the biggest. Here it is ABC + CDA = 200 • and the quadrangle will be split along [BD]. The parameter ϵ remains to be found and can be defined by the user. The value of ϵ will be discussed in the next section.

Aligned points

As stated in Property 1, for any number of aligned points there exists no triangulation. If a subset of our centroids is aligned, this will create a zone of instability as this subset will be difficult to triangulate. Furthermore, we just stated that there is an error margin on angle measurements. This increases the zone of instability due to aligned points. Let us consider the two situations of Figure 5, and the point of view of the edge [BD].

Situation 5a occurs when ABD + ADB < ϵ. In this case, the edge makes a flat triangle with A. This should be triangulated the other way (with [AC] splitting the quadrangle). The situation 5b is a proper triangulation. However, it could very well have been triangulated the other way around with [AC] splitting the quadrangle. This situation occurs when π + ϵ > ABD + DBC > π -ϵ.

We perform similar tests on both sides of the edge and with both vertices of the edge. This defines the zone of To prevent this situation from occuring too often, one should try to segment text columns rather than text paragraphs or text lines. Text lines and paragraphs are usually aligned in the same column.

Ordering implicit threshold

The algorithm to transform the Delaunay triangulation into a graph contains a step when the children of a node are ordered. This step contains an implicit threshold. With the notations of Figure 3, let us consider that -→ Ax, -→ AC < -π + δ. If we make an angle measurment error of ϵ > δ then we can have -→ Ax, -→ AC < -π. This angle will be congrued back

inside [-π; π] to become -→ Ax, -→ AC + 2π < π.
This changes the ordering of C from being the first to being the last child.

To deal with this, we define an instability zone equal to [-π; -π+ϵ]∪[π-ϵ; π]. If one or more children are within this zone of instability, we change the ordering of the children of the current node by performing a circular permutation. We then try to match all the possible orderings of the graph.

Matching

Now that we have identified all the sources of instability, we can test all their combinations to match the layout L.

When combining several instabilities we recompute them. By instance, we apply one instability. Then we recompute the instabilities and only after that do we apply a second instability. This is motivated by the fact that applying one instability in a quadrangle can create new instabitilities for the edges of the quadrangle.

The number of instabilities due to the Delaunay triangulation can be rather big (up to 28 in our experiments). As the combinatorial of their combinations will grow exponentially, we limit the number of simultaneous instabilities to a value n. By instance, if n = 2, we will only consider the cases when a maximum of two instabilities occur in the layout.

The ordering instabilities are quite rare as we start from the top left corner and they occur for the children on the left of the current node. Hence we will test all the ordering instabilities. The matching procedure becomes: Match ( layout L , database S , angle ϵ, nbInstabilities n ) list of indexes Matches Matches . add ( find L in S ) for all d elauna yI nstab i liti e s (ϵ, n ) modify L for all or d er in gIns ta bilit ie s (ϵ) modify L Matches . add ( find L in S ) end for end for return Matches

As the instabilities can be different from one layout to another, the matching algorithm is not symmetric e.g. matching a layout L1 with a layout L2 may not produce the same results as matching L2 with L1.

EVALUATION

This section presents the metrics and the dataset we used for the evaluation of the Delaunay Layout Descirptor.

Metrics

We chose to evaluate the Delaunay Layout Descriptor with three criteria. The stability is the prime criteria for security applications. It is usually quantified with the probability of false positives. We studied a second scenario based on document classification and retrieval. This scenario contains two metrics: precision and recall. Finally, we also took into account the computational complexity of the descriptor.

Probability of false positives

The probability of false positives (PFP) is the probability that two identical layouts cannot be matched together. They will be considered different and potentially fraudulent. If this probability is too high, too many documents will have to be manually verified and the system will be too expensive and useless. The PFP of the layout descriptor will also be a lower boundary for the PFP of the segmentation algorithms that we could want to evaluate. The PFP should be as low as possible. It is equal to 1 -stability.

We consider a set of k copies of the same layout. We want to match one against all. This produces k -1 matches. We consider that a copy of a layout will not occur twicescanning a document twice never produces the exact same image. Hence we should not match a layout copy with itself and we substract one match.

Assuming t matches fail, the probability of false positives is equal to:

P F P = t k -1 (1)
We then take the average of the PFPs for all the copies of all the layouts.

Classification and retrieval scheme

In this scenario we compute the descriptors for a database of layout copies to obtain a set of m descriptors S. Some layout copies can of course have the same descriptor. Then we match each layout copy with this set of descriptors.

For a given query (layout copy), we are supposed to retrieve k layouts copies. Here we include matching the query with itself as this is a classification task. Out of these only q = k -t are retrieved and an extra p wrong results are retrieved.

The precision and recall are given for one query by:

P recision = q q + p (2) Recall = q k -1 = 1 -P F P × k -1 k (3)
A precision of 1 means that no wrong results are returned and a recall of 1 means that all the right results are returned. We will also use the classification accuracy which can be computed for the whole dataset (m layouts and m queries):

CAccuracy = 1 m m ∑ i=1 qi ( 4
)
Where qi is q for the i th query.

Computational complexity

The computational complexity is of interest for both the computation of the descriptor and the matching of the descriptor. They are usually dependant on the number of regions in the layout and the number of documents in the database respectively.

We will also look at the size of the descriptors. This parameter is important as it affects the size of the signature and it also affects the size of the index if we want to index a database. To test our algorithm we created a database of 15 layouts similar to the ones in Figure 6. These layouts are the results obtained by three segmentation algorithms PAL [START_REF] Chen | Hybrid page segmentation with efficient whitespace rectangles extraction and grouping[END_REF], JSEG [START_REF] Deng | Unsupervised segmentation of color-texture regions in images and video[END_REF] and Voronoi [START_REF] Kise | Segmentation of page images using the area voronoi diagram[END_REF] on the documents of the PRiMA dataset [START_REF] Antonacopoulos | A realistic dataset for performance evaluation of document layout analysis[END_REF]. Among these 15 layouts two of them are identical but obtained with a different segmentation algorithm: they have the same number of regions with approximately the same size and the same positions. The layouts contain between 6 and 28 regions. For PAL we only used the block information as we have already stated that text line segmentation will create too much instability.

Testing dataset

Figure 7 represents the creation process of the dataset. We printed each layout twice on one printer (arrow number 1). Then we photocopied the prints (arrow 2) making 4 pages (2 prints + 2 copies). We photocopied these four pages again (arrow 3) making 8 pages (2 prints, 4 copies, 2 double copies). We then scanned in black and white these pages twice on two scanners (arrows 4 for first scanner and 5 for the second) making 32 layout images. We repeated this process with an other printer making a total of 64 images of the same layout. The total size of the dataset is then 15 × 64 = 960 images. The scanners added salt and pepper noise which created many regions made of one or two pixels. Such noise would not be produced by a segmentation algorithm and we removed it from the dataset.

The dataset contains scale variations as the printers add margins around the layout images and hence change their scale. We also used batch scanners that have introduced a surprisingly significant amount of skew (about 5 -10 • ). This dataset will allow us to test the robustness and stability of our descriptor to real print and scan noise. It is available on http://navidomass.univ-lr.fr/LayoutCopies/.

RESULTS

We compare the results of our descriptor with three other methods: the one of Gordo and Valveny (G & V) [START_REF] Gordo | A rotation invariant page layout descriptor for document classification and retrieval[END_REF], the one of Bagdanov and Worring (B & W) [START_REF] Bagdanov | First order Gaussian graphs for efficient structure classification[END_REF] and the one of Nakai et al. (LLAH) [START_REF] Nakai | Use of affine invariants in locally likely arrangement hashing for camera-based document image retrieval[END_REF]. Table 1 summarizes all the results except for precision and recall. The symbol ↓ indicates that the metrics should be as low as possible to be good and ↑ means the contrary.

Probability of false positives

Intrinsic PFP

If we try to find an exact match for the descriptors without any matching algorithm we obtain what we call the intrinsic probability of false positives (iPFP).

As there has not been any previous evaluation of the stability of a layout descriptor we implemented the descriptor of Gordo and Valveny [START_REF] Gordo | A rotation invariant page layout descriptor for document classification and retrieval[END_REF] and tested it for comparison without any matching algorithm. The descriptor contains four informations:

• The angle between the edge joining the centroid of a region and the centroid of all the regions and the horizontal x axis

• The length of this edge

• The area of the region

• The type of the region (text or non text)

We only used the first three informations and set the fourth one to text all the time as it was not available. This will only increase the stability of the descriptor as there will be one less variable per region. Gordo and Valeveny's descriptor has an iPFP of 1 while the Delaunay Layout Descriptor has an iPFP of 0.26. The result for Gordo and Valveny's descriptor is expected as they use numeric values. Changing any angle/length/area by one pixel will change the descriptor and make it unstable. This would be the same for any other descriptor based on voting or distance computation. We did not implement Bagdanov and Worring's algorithm or LLAH as we are very confident they would produce the same results. They both use "continuous" values which will lead to a very high level of instability.

) O(n log n) O(n log log n) O(n) Size of the descriptor ↓ O(1) O(n) O(n) O(n) Computational cost of matching ↓ O(1) O(m) O(m) O(

PFP

The matching algorithm has two parameters: the error on the angle measurment that we accept and the maximum number of instabilities that can occur at the same time. The angle error related to the digitization of the images can be estimated to be below ϵ = 5 • . We found experimentally that the angle variation introduced by the use of a second segmentation algorithm for the same layout is 10 • ≤ ϵ ≤ 15 • . We tested the algorithm with n = 1, n = 2 and n = 3 instabilities. We did not try to have more combinations as the results were already perfect up to the fifth decimal. Figure 8 summarizes the results. The lines are named PFP5 • or PFP15 • according to the value of ϵ. The adjunction of an s (PFPs) means that each layout is the result of only one segmentation algorithm and we removed the duplicate layout that was the results of a second segmentation algorithm. The vertical scale is logarithmic.

Having two instabilities at the same time is enough to have a PFP below 1%. One can also notice that a 5 • angle error is sufficient if we use one segmentation algorithm per layout. Two different layouts can be segmented with different algorithms. This situation is usually the case in a digitization framework. These values are (almost) perfect and don't need to be improved any further. Since there is no point in achieving a PFP lower than the one we achieve we do not find it necessary to compare it with the other algorithms.

Classification and retrieval

Precision and recall

Similarily to what we did for the probability of false positives, we can compute the precision and recall of our system. The precision is always 100%. The recall is shown in Figure 9 for the same cases as the PFP.

Once again these results are nearly perfect and don't need to be improved.

Classification accuracy

As the other authors do not provide any probability of false positive, precision or recall for their method, we also use the one they provide. Gordo and Valveny [START_REF] Gordo | A rotation invariant page layout descriptor for document classification and retrieval[END_REF] achieved 0.66 classification accuracy on a dataset of 823 documents. Bagdanov and Worring [START_REF] Bagdanov | First order Gaussian graphs for efficient structure classification[END_REF] achieved 0.99 classification accuracy on 857 documents. LLAH [START_REF] Nakai | Use of affine invariants in locally likely arrangement hashing for camera-based document image retrieval[END_REF] achieved 0.98 retrieval accuracy on 1000 images. LLAH is not originally made for classification purposes as it only and always retrieves one result per query hence the authors do not provide any classification accuracy. The accuracy used by LLAh is defined by

RAccuracy = 1 m m ∑ i=1 ti ( 5
)
Where ti is a binary value equal to 1 when the result is correct. This is the limit case of a classification accuracy in the case where only one result is retrieved and each class is a singleton. Thus, we can use it.

For the Delaunay Layout Descriptor (DLD), the classification accuracy is always 1 except if we try to classify the whole dataset with an angle tolerance of 5 • . If we consider the scheme of LLAH, our accuracy is 1. We always retrieve at least one identical layout.

Computational cost

We consider that n is the number of regions in a document and m is the number of layouts in the database.

Descriptor computation

The worst case computational cost of the Delaunay triangulation is O(n 2 ) as implemented in opencv 2.4.9 1 but it can brought down to O(n log n) with the sweep line algorithm [START_REF] Leach | Improving worst-case optimal Delaunay triangulation algorithms[END_REF]. For most cases, it will actually be O(n log log n). The transformation of the Delaunay triangulation into an ordered graph costs O(n) as each centroids is processed once. The total computational cost of the descriptor is then O(n 2 ) in its current implementation and it can be optimized to O(n log n) and to O(n log log n) in the general case.

Gordo and Valveny's descriptor can be computed in O(n log n) because of the sorting algorithm required to sort the features by ascending order of their first value. Bagdanov and Worring's can be computed in O(n log log n) in the general case as they also make use of the Delauny triangulation to compute the Voronoi diagram of the layout. LLAH can be computed in O(n) as each region is only processed once independantly from the other regions.

Size of the descriptor

The DLD has a constant size, hence its memory size is O(1) with respect to n. The other descriptors are computed region wise and hence, use a memory size of O(n).

Matching computation

Regarding the matching of one layout with the database, for the DLD it can be achieved in O [START_REF] Álvaro | A shape-based layout descriptor for classifying spatial relationships in handwritten math[END_REF] with respect to m. This is due to the use of cryptographic hashing (we are looking for an exact match) and is similar to LLAH. The two other descriptors require O(m) computations as the query needs to be matched on a one by one basis with all the layouts in the database.

Experimental results

In a practical case, there are two main criteria to compare algorithms: how much time do they take to execute and how much memory do they require.

Matching time

Computing the descriptor on an Intel Core i7 3740QM with 8 cores at 2.7GHz takes on average 12 milliseconds. Matching a layout with the whole database with an angle error of 5 • an a maximum of 2 simultaneous erros takes on average 0.1 seconds and 1.5 seconds with 3 simultaneous instabilities. If we use an angle error of 15 • , these values go up to 0.8 and 23.9 seconds respectively. It should be noted that this matching time is independant from the size of the database and could be improved as the computation 1 opencv.org of the instabilities and of their combinations has not been optimized at all.

Gordo and Valveny's algorithm takes 5s to match a query. Bagdanov and Worring's algorithm and LLAH take respectively 0.05 to 0.3s and 0.05s.

Memory usage

While the memory usage should be directly related to the size of the descriptor, its practical implementation and implementation constraints can change it significantly. One should keep in mind that two descriptors using respectively n bits and 1000 × n bits scale up with O(n). Yet one uses a thousand times more memory than the other.

To compute this metrics for all descriptors, we assume a database of one million layouts and 20 documents/images per layout. This makes a database of 20 million documents. We also consider that each document contains 12 regions on average and that an integer is stored on 32 bits (or 4 octets) of memory. The values in brackets in Table 1 indicate theoretical values while the other values are obtained experimentally.

The memory space taken by the DLD can be 128 bits for non secure applications and 256 bits for secure applications. Each layout will then require (128 + 20 × 32)/8 = 96 octets. 128 bits for the descriptors and 20 × 32 bits for the 20 numbers of the associated documents. The whole database will then require 96Mo. This value does not take into account implementation constraints such as memory alignment and storage structure (unordered map in our case). We created an index for a virtual database and it uses 284Mo of memory.

Gordo and Valveny's descriptor contains 4 values per region plus one value to identify the document. Hence the theoretical size of the databse would be (4×12+1)×4×20e6 = 3.9Go. Experimentally we obtained a size of 4.7Go.

The descriptor of Bagdanov and Worring uses 6 integers per region. It also creates a graph for each document. The database is made of prototype graphs that represent each class of layout. We would need to have an estimate of the number of graphs per class and of edges per graph to estimate the memory requirement to index the database. We have none of these value and thus prefer not to make an estimate.

LLAH stores one hash (one integer) per word in the document. In Takeda et al.'s paper they consider a normal number of words to be 200 words. Each word is associated to a document which means that there are two integer values per word: the hash and the number of the document.Hence the theoretical size of the index is 2×4×200×20e6 = 32Go. This value neglects the possible collisions e.g. the words that have the same hash. For each collision, there is one hash/integer less to store. Experimentally, Takeda et al. obtained a size of 120Go.

Domain of application

When using or choosing an algorithm it is important to know what are the constraints for its use and what it can be used for.

The number of possible simultaneous instabilities increases with the number of edges and in consequence with the number of regions. Raising the number of simultaneous instabilities increases exponentially the number of combinations to test. It would then be computationnaly prohibitive to match the Delaunay Layout Descriptor for documents that contain more than 30 or 40 regions.

As we have seen LLAH works best with at least 200 or so words. We can safely assume that it does not work properly if there are less than 100 regions. There would not be enough points to properly describe the document.

The other descriptors do not seem to have any specific limitations with respect ot the number of regions.

Since the Delaunay Layout Descriptor is the only one that can be used with any cryptographic hashing, it is also the only one that can be used for secure applications.

DISCUSSION

One could wonder about how much the adjacency matrix of the delaunay triangulation of the layout is representative of this layout. The performance of the DLD proves this representativeness. The DLD does not use the size of the regions, neither does it use the distance between the centroids of these regions. But, for a mostly convex region, the bigger the region, the further its centroid will be from the other centroids. Hence the area of a region is reflected by the distance between the centroids. The Delaunay triangulation is directly dependent on these distances between the centroids and their relative positions. Hence, the DLD indirectly contains both informations. It is invariant to scale and to a certain extent to rotation. This is expected as rotating a layout too much can change this layout.

Figure 2 :

 2 Figure 2: Example of a delaunay triangulation produced by opencv. The vertices in the center are the centroids of the regions of the layout.

  Del2Graph ( graph G , start vertex v ) vertex list Vl Vl . push ( v ) mark v as done for i =0; i < G . nbVertices -1 vertex list Children for all vertices a in G . adjacentVtx ( Vl ( i )) if a is not done Children . push ( a ) mark a as done end if end for order ( Children ) for all vertices a in Children Vl . push ( a ) end for delete Children end for return Vl The top left corner is a good starting point because the algorithm always generates it. Our algorithm differs from the BFS in the ordering of the children of a given node. Let us consider the situation of Figure 3 where A is a parent node and B and C are its children. x is the horizontal axis. B and C are ordered by increasing value of the angles -→ Ax, -→ AC and -→ Ax, -→ AC in [-π; π]. Here, both angles are negative and C comes before B.

Figure 3 :

 3 Figure 3: One node with two children

Figure 4 :

 4 Figure 4: Example of a quadrangle that needs to be triangulated One immediate source of instability comes when the sums are both equal to 180 • . This means that all four vertices are on the same (circum) circle and there are two possible triangulations of the quadrangle. This explains Property 3. The situation worsens in the digital world due to the discretization of of the coordinates in the integer pixel values. This introduces an error on the angle measurements which needs to be taken into account. There exists an instability area when a couple of opposing angles forming a quadrangle have a sum within [180 • -ϵ; 180 • + ϵ]. If this is the case, we will flip [AD] to [BC] and try to match both possibilities of splitting the quadrangle.The parameter ϵ remains to be found and can be defined by the user. The value of ϵ will be discussed in the next section.

  (a) [BC] makes a flat triangle (b) [AC] could make a flat triangle

Figure 5 :

 5 Figure 5: Two situations with nearly aligned points

Figure 6 :

 6 Figure 6: Three layouts produced by PAL, JSEG and Voronoi from left to right.

Figure 7 :

 7 Figure 7: The creation process of our dataset.

Figure 8 :

 8 Figure 8: The values of the PFP for different situations and sets of parameters.

Figure 9 :

 9 Figure 9: The values of the recall for different situations and sets of parameters.

Table 1 :

 1 Summary of the results

	Metric	DLD	G & V	B & W	LLAH
	iPFP ↓	0.26	1.00	NA	NA
	PFP ↓	0.00	NA	NA	NA
	Classification accuracy ↑	1.00	0.66	0.99	0.98
	Computational cost of descriptor ↓ O(n log log n

CONCLUSION

In this paper we present a stable document layout descriptor (Delaunay Layout Descriptor) based on a Delaunay triangulation of region centroids. It comes with a matching algorithm to obtain outstanding performances.

We have shown that it improves the state of the art in every aspect except for the matching time which could be improved. Its stability, precision, recall and accuracy reach 100%. It also reduces by a factor 400 the memory required to index a document database and can match a document against a database of any size in less than a second up to 28 seconds depending on the required level of performance.

When using the Delaunay Layout Descriptor, one should have in mind one tip to leverage all its power. The segmentation algorithm should not produce too many aligned regions. Hence, it should not segment text lines but rather text paragraphs or even better: text columns. Our test dataset contains layouts with as little as 6 regions and as much as 28 regions which proves that the descriptor should work in most cases.

Finally, the Delaunay Layout Descriptor is fast, stable, robust, precise and concise beyond all expectations. From our point of view, it solves the issue of describing a layout. Its implementation could probably be improved as it has not been extensively optimized especially regarding the combination of the instabilities. The next challenge is to have a segmentation algorithm with the same level of performance as it is no use to match a layout if the layout is wrong or unstable. We could have attempted to create such a segmentation algorithm before but the analysis of the stability of a segmentation algorithm requires an extremely stable tool to compare the layouts it produces. This is why we created the Delaunay Layout Descriptor before trying to design a stable segmentation algorithm.


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

Petra Gomez-Krämer

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

Let's be done with thresholds !

Current security applications rely on the performances of the algorithms that they use. For document authentication, document analysis algorithms should be precise enough to detect any modification. They should also be stable enough so that a document and its photocopy yield the same result. This requirement is an absolute stability. Having close values is not enough. They need to be exactly the same. This paper presents our preliminary work on the case of a stable layout descriptor. While everyone knows that thresholds are a source of instability, they are still common practice. We describe a promising layout descriptor which drastically reduces the number of thresholds compared to the state of the art. Unfortunately, it is not stable when tested on real data. There are still too many thresholds. This paper opens and justifies the path towards algorithms without any threshold.

I. INTRODUCTION

Many documents need to be secured, ideally by the means of an electronic signature. If two documents have the same signature, then they are authentic copies of each other and if their signatures are different, one of the two documents is fraudulent or at least different from the other one. This concept works well for naturally born digital documents. However, nowadays a document, the so-called hybrid document, is often used in electronic or paper form according to the need. Hence, the hybrid document undergoes a lifecycle of printing and scanning and thus different degraded versions of the document exist as the printing and scanning process introduces specific degradations, such as print and scan noise, in the document [START_REF] Kanungo | Global and local document degradation models[END_REF]. Thus, the concept of electronic signature can not be applied. For this reason, our work intends to develop an advanced electronic signature for the field of securing hybrid documents, the so-called hybrid security. Our idea is to extract the layout, the text and the images from the document to compute a stable signature that will be the same for all the authentic copies of the document. Here, we consider that an authentic copy, should have the same layout as the original.

To our knowledge, the closest work is a signature [START_REF] Garcià | Secure Imprint Generated for Paper Documents (SIGNED)[END_REF] based on pixelwise signal analysis techniques which is not satisfactory because of its large size. Other signatures such as the 2D-Doc [START_REF] Ants | Spécifications techniques des Codes à Barres 2D-Doc[END_REF] require the emitter of the document to provide the information used for signature computation, e.g. the name and the address of the beneficiary, and thus secures only partially the document (the provided information, but for instance not the layout). Thus, an ideal signature computation process is to automatically extract the content of the document (text, layout, graphics) and use it in the signature computation. A smaller signature than [START_REF] Garcià | Secure Imprint Generated for Paper Documents (SIGNED)[END_REF] will result as the amount of information to be secured is smaller since the image is not processed pixelwise. Anyhow, this signature will still allow to secure the whole information of the document. In consequence, this requires a layout descriptor that is stable with respect to print and scan noise so that two copies of the same document can have the same signature. This paper describes such a layout descriptor which, to our knowledge, is unique.

Because of the specific security context we will now precise two pairs of concepts that should not be confused: the difference between the segmentation and the layout as we understand it and the difference between accuracy and stability.

According to [START_REF] Chaudhuri | Digital document processing. major directions and recent advances[END_REF], the physical layout of a document refers to the physical location and boundaries of various regions in the document image. The physical layout extraction typically relies on a page segmentation algorithm. The page segmentation computes the boundaries of the various regions in the document image. Then, based on these boundaries, the layout extraction determines the spatial relationships between these regions. We simplify the above definition by only keeping the physical locations of the regions for the layout. We consider that the position of the region boundaries is the page segmentation. Thus, we consider that the three segmentation results shown in Figure 1 have different segmentation results but identical layouts. The two other concepts that should not be mixed up are accuracy and stability. Accuracy requires a groundtruth to evaluate how close a result is to this ground truth. Accuracy can be evaluated with only one result as long as there is also a ground truth. Stability does not require a ground truth. Stability requires at least two results with similar inputs to see how close these results are together compared to how close the inputs were. In our case, similar inputs are photocopies of the same document. A consequence of this is that an algorithm can be very stable and yet not be accurate. For instance an algorithm that always makes the same mistakes or in the case of a segmentation algorithm, an algorithm producing always one region covering the whole image. Such an algorithm would have an absolute stability and zero accuracy. The contrary is not true. An algorithm with an absolute accuracy will always produce results that are identical to the ground truth and hence identical between each other. A perfect segmentation algorithm will also be perfectly stable.

In order to have the smallest possible signature, the best solution is to have a perfectly stable descriptor. This allows the use of cryptographic hashing such as SHA256 [START_REF] Bryson | Secure Hash Standard (SHS)[END_REF] which reduces the size of the signature to 256 bits while providing a good level of security. Considering two documents, either their layout signatures are exactly the same and the documents have the same layout or they are not the same and the documents have different layouts. There is no measure of closeness of their layouts as this is not necessary for our application (a document cannot be half authentic).

We can now consider the state of the art under this new perspective in Section II. Then we will introduce our decriptor and the new set of spatial relationships on which it is based in sections III and IV. In section V we show an example of the computation of the descriptor and in section VI we study the stability of this descriptor. The last section discusses the descriptor and concludes.

II. STATE OF THE ART

The Description and MOdification of Segmentation DMOS with the EPF grammatical language [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] offers an original layout description. It extracts content from a document by identifying its layout. The DMOS paradigm requires the user to define the layout with EPF a priori and is not based on the content of the document image to be processed. Hence the layout description is not adaptive to the layout of the document at hand.

Álvaro and Zanibbi [START_REF] Álvaro | A shape-based layout descriptor for classifying spatial relationships in handwritten math[END_REF] propose a layout descriptor for handwritten math expressions. They use a polar histogram and a support vector machine to classify the spatial relationship between two elements. There are five classes: horizontal, superscript, subscript, below, and inside (e.g. in a square root).

The other layout descriptors are made for document classification and retrieval. The MPEG-7 standard [START_REF] Kasutani | The MPEG-7 color layout descriptor: a compact image feature description for high-speed image/video segment retrieval[END_REF] includes a color layout descriptor. It divides an image into an 8 by 8 grid, takes the mean color value of the grid, converts it into the YCbCr color space and runs a discrete cosine transform on it. Esposito et al. [START_REF] Esposito | Multistrategy learning for document recognition[END_REF] use a set of 7 quantized position and size attributes (e.g. width, height, on top of) whose values can make 171072 combinations. Cesarini et al. [START_REF] Cesarini | Encoding of modified X-Y trees for document classification[END_REF] modify the X-Y cut algorithm and use the cut sequence to encode the layout. This descriptor is tied to the segmentation algorithm and hence not very useful in a general case. There are also many graph based layout descriptors [START_REF] Gordo | A rotation invariant page layout descriptor for document classification and retrieval[END_REF]- [START_REF] Bagdanov | First order Gaussian graphs for efficient structure classification[END_REF] using features such as distance, size, position, angles and other metrics.

[] proposes to store the structure of the document in a dendogram, they also use geometrical and local features. Unfortunately, they do not use any spatial information other than inclusion which is not enough for a layout descriptor. Some of these descriptors are made to be robust to noise, rotation and scale. By instance, Gordo and Valveny's descriptor [START_REF] Gordo | A rotation invariant page layout descriptor for document classification and retrieval[END_REF] is invariant to scale and rotation. Unfortunately, by 'invariant' the authors mean reasonably invariant. E.g. if we consider two copies of the same document, a small difference is accepted as long as the descriptors of the copies can be matched. This 'weak' invariance is not enough for security application which require an exact invariance, e.g. the values of the descriptor should remain the same. We explain this in the next section.

III. OVERVIEW OF THE DESCRIPTOR

The instability of an algorithm will occur with every possibility of changing the output. Hence using many thresholds or metrics that can take many values such as a distance or an area will lead to an unstable algorithm. By instance, continuous values such as 0.1234 and 0.1235 are close but different and reflect a form of instability. This brings us to the main tradeoff when designing any stable descriptor. On the one hand, the more precise the information and the more information is included in the descriptor, the more unstable the descriptor will be. On the other hand, the less precise and the less information is in the descriptor, the less useful the descriptor will be. This why we decided to use only 9 spatial relationships and no size information. We consider this to be the bottom limit for the amount of information to include and we don't want to add more to be as stable as possible. These relationships are described in the next section.

When computing the descriptor, we consider that a segmentation algorithm has already been run on the document and the document regions are already identified. The task of the descriptor is to describe the spatial relationships between all these regions. This is done by comparing the position of one region with all regions including itself. The result can be viewed as a totally connected directed graph whose vertices are the regions and whose edge attributes are the spatial relationships. It can also be viewed as a matrix M , where M i,j is the spatial relationship of region i with respect to region j. We use this last representation.

IV. DESCRIPTION OF SPATIAL RELATIONSHIPS

The easiest way to describe a layout is through a set of relations like Allen's algebra [START_REF] Allen | Maintaining knowledge about temporal intervals[END_REF] or RCC8 [START_REF] Cui | Qualitative and topological relationships in spatial databases[END_REF]. RCC8 describes spatial relationships of regions using 8 basic relations such as disconnected or partially overlapping but neglects any directional information (left, right, above, below). However, Allen's algebra defines 13 spatial relations based on interval intersection including the notion of left and right. These relations can be extended in two dimensions with a topological product (combination of the relationships on each axis x and y) making 13 × 13 = 169 relations allowing to precisely characterize the relationship between two regions. Nevertheless, they are too numerous and will not be stable in our case, especially those describing superimposition of bounding box borders, as Allen relations are solely based on the position of bounding boxes. In case of print and scan noise, the segmentation borders and the bounding boxes of different copies of a document vary slightly and practically never superimpose exactly.

For this reason, we propose modified Allen relationships. We use the centroid of a region instead of the bounding box borders as it is much more stable in case of noise. For the simplicity of explanation, we consider now only the horizontal relationships of two regions r 1 and r 2 . There are three possible relationships of r 1 with respect to r 2 : r 1 left to r 2 (left), r 1 overlaps r 2 (center) and r 1 right to r 2 (right). Let L i , C i , R i be respectively the coordinates of the left corner, of the centroid and of the right corner of the bounding box of region r i as shown on Figure 2. W i = R i -L i is the width of the bounding box. Hereafter, we consider the position of the centroid of r 1 with respect to the bounding box of r 2 . The algorithm below details how we decide which is the relation of r 1 with respect to r 2 .

if L 2 ≤ C 1 ≤ R 2 relation = center elseif C 1 < L 2 relation = left elseif R 2 < C 1 relation =

right end

These spatial relationships can be extended to 2D with a topological product as shown in Table I. Top and bottom are the vertical equivalents of horizontal left and right relationships respectively. The values in the table are the index for each relationship. By instance if the relation between r 1 and r 2 has a value of 1, this means that the centroid of r 1 is in the top left position with respect to the bounding box of r 2 . Thus, we have reduced the 169 original relations to 9. We call the matrix of the descriptor, the layout matrix. The computation of the layout matrix requires some preprocessing. For this example we consider the segmentation output of Figure 3. First we extract its connected components. Each connected component corresponds to a region of the document. Then we remove the background region e.g. any component whose dimensions are the same as the image. We number arbitrarily the remaining connected components/regions as shown in Figure 3.

Left Center

Once, the regions are determined, the position of each region is compared to all the regions (including itself). Then, the layout matrix M is constructed as follows:

M i,j = A(r i , r j ) (1)
where A(r i , r j ) is the index of the modified Allen relation in Table I when comparing the position of r i with respect to r j . For instance, when comparing r 1 to itself, we obtain M 1,1 = A(r 1 , r 1 ) = 5 as the position of the two regions is exactly the same. When comparing r 1 to r 2 we obtain M 1,2 = A(r 1 , r 2 ) = 3 as the centroid of r 1 is on the top right of r 2 . For the example layout of Figure 3, we obtain the layout matrix of Table II. Finally, we sum each line to reorder the numbering LAYOUT MATRIX of the connected components and the layout matrix so that the sums are in ascending order. This allows to order the regions from top to bottom and left to right. This step is not necessary in our example since this is already the case.

VI. STABILITY ANALYSIS

A. Stability of the spatial relationships

Concerning the stability of this layout descriptor, there are four distortions: print and scan noise, scale, translation and rotation. Print and scan noise is not present in the result of a segmentation algorithm. Scale and translation have no influence on the relative spatial relationships. The rotation remains.

To study its impact we consider a typical segmentation output shown on Figure 4. Based on the output of Figure 4 we model the situation with the notations of Figure 5. Region 2 is on the left and region 1, on the right. The centroid of r 1 , F, is the origin of the coordinate system. Since the regions are text lines, we consider that the centroid of r 1 is in the middle of its bounding box.

The coordinates of the points A, B, C and D are:

A = ( x 1 y 1 ) B = ( x 1 y 2 ) C = ( x 2 y 2 ) D = ( x 2 y 1 ) (2)
We consider the position of r 1 with respect to r 2 . With a null rotation, the spatial relationship along the y axis between is "center". We now apply a rotation of angle θ ∈ [0 • ; 90 • ] and of center F on the document. The center of the rotation can be chosen arbitrarily and the computation will be easier if it is F. The new coordinates are computed by multiplying the old ones by a rotation matrix:

R(θ) = ( cosθ -sinθ sinθ cosθ )
The images of A, B, C and D are respectively denoted A', B', C' and D'. We only need their ordinates:

y A ′ = x 1 sinθ + y 1 cosθ y B ′ = x 1 sinθ + y 2 cosθ y C ′ = x 2 sinθ + y 2 cosθ y D ′ = x 2 sinθ + y 1 cosθ (3)
It is obvious that y D ′ is the maximum ordinate as x 1 < x 2 , y 2 < y 1 and the sinus and cosinus are positives (θ ∈ [0 • ; 90 • ]). θ is comprised between 0 • and 90 • so the spatial relationship along the y axis will change when

y D ′ < 0 (4)
We can rewrite equation 4:

sinθ cosθ < -y 1 x 2 ⇔ θ < arctan ( -y 1 x 2 ) = 2.7 • (5)
Thus our layout descriptor will produce the same output independantly from scale, translation or rotation up to 2.7 • of rotation. This is sufficient for a flatbed scanner and were it not, one could use a deskewing algorithm. Current skew estimators have a precision below 0.1 • [START_REF] Papandreou | Document Image Skew Estimation Contest (DISEC13)[END_REF].

B. Stability of the layout matrix

The layout matrix is sorted in ascending order of the sum of its rows. Thus, assuming that the spatial relationships between the regions are stable, the only occurence of instability is when two rows i and i + 1 have the same sum. We will assume that two such rows exists and prove that this leads to a contradiction.

The most obvious case is when the two rows are identical. This requires M i,i+1 = M i+1,i+1 = 5 and M i+1,i = M i,i = 5. This means that the regions are superimposed or that one region is around the other. This is not the case in most documents. And if we use the image of the segmented regions to extract them we never obtaion two superimposed regions. If two regions superimpose exactly, they will be considered as one and if they superimpose partially, they will be split into non superimposing regions.

Let us now consider the case when the regions are not superimposed. We can choose arbitrarily M i,i+1 < 5 < M i+1,i . The equality of the sum of the rows requires that there exists a region k such that M i+1,k > M i,k .

We will now prove the following lemma which will in turn prove the impossibility of the above statement.

Lemma 6.1: ∀{i, j, k} M i,k < M j,k ⇒ M i,j ≤ 5
To simplify the demonstration, we will consider the unidimensional case with the same notations as Section IV. There are three cases:

1) M i,k = lef t (1) and M j,k = center (2) 2) M i,k = lef t (1) and M j,k = right (3) 3) M i,k = center (2) and M j,k = right (3)
The first case is equivalent to

C i < L k ≤ C j ⇒ L i ≤ C j ⇒ M i,j ≤ 2 (center) (6)
Which is the expected result for a unidimensional case. The reasoning is the same for the two other cases.

Using Lemma 6.1, M i+1,k > M i,k implies that M i+1,i ≤ 5 which is impossible. Hence the layout matrix is perfectly stable with the exception of documents were one region is surrounded by another.

C. Experimental analysis

One method to confirm our theoretical findings could have been to print, photocopy and scan real documents and then apply several segmentation algorithms on them. But to our knowledge, there is no perfect segmentation algorithm hence the segmentation results would already produce different layouts for the copies of the same document. It would then be pointless to try to have identical descriptors for all of them. We separate the problem of layout description from segmentation with a layout data set. We took 14 segmentation outputs as initial layouts, which we copied to reflect the geometric distortions/noise of a real document to be independent from the segmentation performance. We printed each layout twice. Each print was photocopied twice making 2×2 = 4 copies plus two originals. The first photocopy of each original was photocopied again adding an extra two copies and making 8 paper pages for each layout. These pages were scanned twice in gray level at 600dpi. This produces 16 images of each layout. Then we binarized the scanned images using Otsu's method [START_REF] Otsu | A threshold selection method from graylevel histograms[END_REF] to obtain perfect segmentation results on which we could apply our layout descriptor. Four examples of these results are shown in Figure 6. This method has the advantage of reflecting the impact of print and scan degradation on the layout of the document image while ensuring the perfect stability of the layout of the segmentation results. The next step was applying our layout descriptor on this dataset to see if it would take exactly the same values on all the copies of each layout. As a matter of fact, it did... for three layouts. The state of the art algorithms would all have failed for all the images because they all use continuous values which makes them completely unstable. Hence our result is already better than the state of the art. Yet, this is not sufficient at all.

During this experiment we noticed that the main cause of instability was the fact that text lines of adjacent columns are I).This will cause the instability of the algorithm. This example can be extended to the case of two regions (not necessarily text lines) that are side by side or on top of each other.

VII. CONCLUSION

The descriptor we have proposed fits many cases for document layout description. Theoretically, it produces exactly the same output up to 2.7 • of rotation and as long as no region is surrounded by another region. If the segmentation algorithm produces text regions instead of text lines or if the text lines are grouped into paragraphs, the descriptor will be even more stable. It is scale and translation invariant. It is adaptable to and independant from any segmentation algorithm. This is achieved through a severe reduction of the number of thresholds. Yet, our experimental analysis proves that the presence of any threshold will lead to an unstable algorithm. Although it is more stable than the state of the art could be, our layout descriptor makes no exception and is not stable enough.

One lesson to learn from this improvement is that thresholds definitely need to be banned if one wants to reach an industrial level of stability/repeatability. We did not discuss the question of parameters but it is also common knowledge that parameters tend to tune an algorithm for a specific kind of input and thus prevent its scalability to a more general case.

As it is long overdue that we put in practise these old recommendations, we will present a layout descriptor and a segmentation algorithm that have no thresholds or parameters in two other papers.

Fig. 1 .

 1 Fig.1. Three layouts that we consider to be identical

Fig. 2 .

 2 Fig. 2. Notations used

Fig. 3 .

 3 Fig. 3. Example of a document layout with 4 regions

Fig. 4 .

 4 Fig. 4. Example of a segmentation output

Fig. 6 .

 6 Fig. 6. Four of the 14 layouts we used to test the descriptor

TABLE I .

 I

2D MODIFIED ALLEN RELATIONS V. COMPUTATION OF THE LAYOUT DESCRIPTOR

TABLE II .

 II

ACKNOWLEDGMENT

This work is financed by the ANR project SHADES referenced under ANR-14-CE28-0022.