Nicolas Obin

Marco Liuni

ON THE GENERALIZATION OF SHANNON ENTROPY FOR SPEECH RECOGNITION

Keywords: information theory, spectral entropy, speech recognition, expressive speech, voice quality, video games

This paper introduces an entropy-based spectral representation as a measure of the degree of noisiness in audio signals, complementary to the standard MFCCs for audio and speech recognition. The proposed representation is based on the Rényi entropy, which is a generalization of the Shannon entropy. In audio signal representation, Rényi entropy presents the advantage of focusing either on the harmonic content (prominent amplitude within a distribution) or on the noise content (equal distribution of amplitudes). The proposed representation outperforms all other noisiness measures -including Shannon and Wiener entropies -in a large-scale classification of vocal effort (whispered-soft/normal/loud-shouted) in the real scenario of multi-language massive role-playing video games. The improvement is around 10% in relative error reduction, and is particularly significant for the recognition of noisy speech -i.e., whispery/breathy speech. This confirms the role of noisiness for speech recognition, and will further be extended to the classification of voice quality for the design of an automatic voice casting system in video games.

INTRODUCTION

This paper presents a preliminary study on the classification of expressive speech for the elaboration of a voice casting system in the context of video games, and exploits a generalization of the Shannon entropy as a measure of the degree of noisiness of a signal for automatic speech recognition (ASR). The context of video games raises innovative and challenging issues over conventional ASR systems.

Voice casting is commonly used in the audio processing of video games to transfer a video game into various languages with a limited amount of available voices for each language : for each role of the source language, one needs to determine the actor in the target language which is the †This study was supported by the European FEDER project VOICE4GAMES. more similar to the source role. In particular, the objective of a voice casting system differs qualitatively from standard speaker recognition applications : in standard speech recognition applications (speaker identification/verification), the objective is to determine the "vocal signature" of a speaker that is invariant to any potential sources of speech variability. Conversely, the objective of voice casting is to determine the "acting signature" that is invariant across speakers (including voice qualities, vocal effort, emotions/attitudes, and archetypes). In the former, the exclusive invariant is the identity of a speaker, any other sources of variability being considered as noise ; in the latter, the primary invariants are precisely these sources of variations, while the identity of a speaker is secondary, only. Additionally, video games also require processing a large range of speech variability of professional actors -including the use of extreme vocal registers, and some non-natural speech (e.g., cartoons, robots, extraterrestrials) ; large databases (from 20,000 to 40,000 audio files and around 500 roles for a single role-playing video game) ; and large differences in audio recordings duration -from a single filler (e.g., inspirations, screams, ≤ 0.5s.) to complete utterances ( 10s.).

In a previous study, evidence for the use of glottal source characteristics in speech recognition has been provided [START_REF] Obin | Cries and Whispers -Classification of Vocal Effort in Expressive Speech[END_REF], in agreement with other recent studies [START_REF] Kinnunen | On Separating Glottal Source and Vocal Tract Information in Telephony Speaker Verification[END_REF][START_REF] Drugman | On the Use of the Glottal Source for Expressive Speech Analysis[END_REF]. However, the description of glottal source characteristics requires the use of glottal source and vocal tract separation methods, which are still not robust to cover satisfactorily expressive speech and adverse recording conditions. Alternatively, the degree of noisiness may be a simple and reliable measure to capture most changes in the glottal source configuration and to cover a large range of voice qualities [START_REF] Laver | The Phonetic Description of Voice Quality[END_REF]. Additionally, the degree of noisiness of an audio signal (e.g., speech, music, sound events) may be advantageously used as a complementary representation to the standard MFCCs for audio recognition. A number of representations have been proposed to measure the degree of noisiness of a signal, based on entropy measures (SHANNON ENTROPY [START_REF] Misra | Spectral Entropy based Feature for Robust ASR[END_REF], WIENER ENTROPY [START_REF] Johnston | Transform Coding of Audio Signals using Perceptual Noise Criteria[END_REF][START_REF] Dubnov | Generalization of Spectral Flatness Measure for Non-Gaussian Linear Processes[END_REF]) or on harmonic/noise decomposition [START_REF] Griffin | A New Model-Based Analysis/Synthesis System[END_REF][START_REF] Obin | Cries and Whispers -Classification of Vocal Effort in Expressive Speech[END_REF]. This paper exploits the R ÉNYI ENTROPY as a generali-zation of the SHANNON ENTROPY to measure the degree of noisiness of an audio signal (section 2). In particular, R ÉNYI ENTROPY presents the advantage over other entropy measures of focusing either on the harmonic content (a prominent amplitude within a distribution) or on the noise content (equal distribution of amplitudes) -without requiring any harmonic/noise decomposition. A multi-resolution spectral entropy is determined through the integration of spectral entropy over logarithmically distributed frequency regions -similarly to MFCCS. This is adopted in order to represent the audio signal both in terms of locally defined energy and noisiness content over the frequency scale. The proposed representation is compared to other noisiness measures including SHANNON and WIENER entropies (section 3) within a large-scale classification of vocal effort (whispered-soft/normal/loud-shouted) in the real scenario of video games production of multi-language massive role-playing video games (sections 4 and 5).

SPECTRAL ENTROPY

With an appropriate normalization, the power spectrum of an audio signal can be interpreted as a probability density. According to this interpretation, some techniques belonging to the domains of probability and information theory can be applied to sound representation and recognition : in particular, the concept of entropy can be extended to provide a concentration measure of a time-frequency density -which can be interpreted as a measure of the degree of voicing (alternatively, noisiness) of an audio signal. The representation adopted in this study (see [START_REF] Baraniuk | Measuring Time-Frequency Information Content Using the Rényi Entropies[END_REF] for the original formulation) is based on the use of Rényi entropies, as a generalization of the Shannon entropy [START_REF] Shannon | A Mathematical Theory of Communication[END_REF]. In this section, the Rényi entropy is introduced with regard to information theory, and some relevant properties for the representation of audio signals are presented. In particular, the Rényi entropy presents the advantage over the Shannon entropy of focusing on the noise or the harmonic content.

Rényi entropy

Definition 2.1 Given a finite discrete probability density P = (P 1 , ..., P N ) and a real number α ≥ 0, α = 0, the Rényi entropy of P is defined as follows,

H α [P ] = 1 1 -α log 2 N n=1 P α n , (1)
where P is in square brackets to indicate that discrete densities are considered.

Among the general properties of Rényi entropies (see [START_REF] Rényi | On Measures of Entropy and Information[END_REF], [START_REF] Beck | Thermodynamics of Chaotic Systems[END_REF] and [START_REF] Zyczkowski | Rényi Extrapolation of Shannon Entropy[END_REF]), the fundamental ones are here shortly summarized. 1) for every finite discrete probability density P , the entropy H α [P ] tends to the Shannon entropy of P as the order α tends to one.

2) H α [P ] is a non increasing function of α, so :

α 1 < α 2 ⇒ H α1 [P ] ≥ H α2 [P ] . (2)
In case of finite discrete densities, the case α = 0 can also be considered, which simply gives the logarithm of the number of elements in P ; as a consequence H 0 [P ] ≥ H α [P ] for every admissible order α.

3) for every order α, the Rényi entropy H α is maximum when P is uniformly distributed, while it is minimum and equal to zero when P has a single non-zero value.

The main advantage of the Rényi entropies is the dependence on the order α, which provides a different concept of concentration for each value of α : in particular, these measures differ by the reshaping applied to the spectrum coefficients before summing, by means of raising them to the α power. This concept is qualitatively detailed in the following section.

Some Properties on the Representation of Noise/Harmonic Content

The α parameter in equation ( 1) introduces a biasing on the spectral coefficients, which gives them a different relevance in the entropy evaluation of the representation ; this means that different values of α determine different concepts of noisiness. Basically, small α values tend to emphasize the noise content of signal, while large α values tend to emphasize the harmonic content of a signal. Consider a vector D of length N = 100 generating numbers between 0 and 1 with a normal random distribution, and two integers 1 ≤ N part , 1 ≤ R part . Define D L as follows :

D L [n] =          1 if n = 1 D[n] Rpart if 1 < n ≤ N part D[n] Rnoise if n > N part . (3)
where

R noise = Rpart L , L ∈ [ 1 16
, 1], then we normalize to obtain a unitary sum. These vectors are a simplified model of an amplitude spectrum (figure 1) whose coefficients correspond to one main peak, N part partials with amplitude reduced by R part , and some noise, whose amplitude varies proportionally to the L parameter, from a negligible level to the same one of the partials. Such a class of vectors represents more general situations, as the entropy measure is permutation-invariant, so that the order of the coefficients in a vector does not modify its entropy value.

Applying Rényi entropy measures with α varying between 0 and 3, we obtain figure 2, which shows the impact of the noise level L on the evaluations with different values of α. For α = 0, H 0 [D L ] is the logarithm of the number of nonzero coefficients and it is therefore constant. The increment of L corresponds to a strengthening of the noise coefficients, causing the rise of the entropy values for any α. The key point is the observation of how they rise, depending on the α value : the convexity of the surface in figure 2 increases as α becomes larger, and it describes the impact of the noise level on the evaluation ; the stronger convexity when α is around 3 denotes a low sensitivity of the measure to the noise coefficients, as their level needs to be high to determine a significant entropy variation. On the other hand, when α tends to 0 the entropy growth is almost linear in L, showing the significant impact of noise on the evaluation, as well as a finer response to the variation of the partials amplitude. As a consequence, the tuning of the α parameter has to be performed according to the desired trade-off between the sensitivity of the measure to the main peaks and the weak signal components to be observed, as noise in our case.

Multi-Resolution Spectral Entropy

A multi-resolution spectral entropy is adopted in order to provide a representation in which the harmonic/noise content of the signal is determined over locally defined frequency bands -similarly to MFCCS. For each frequency band, the R ÉNYI ENTROPY is measured as :

H (i) α = 1 1 -α log 2
N (i) n=1 |A(n)| 2 N (i) n=1 |A(n)| 2 α ( 4
)
where A(n) is the amplitude of the n-th frequency bin in the considered frequency band, and the denominator on the right side accounts for the normalization of the power spectrum in the considered frequency band into a probability density function.

In this study, the R ÉNYI ENTROPY has been computed over 25 Mel-frequency bands. A study-case of multiresolution Réyni entropy for whispered and shouted speech is provided in figure 3.

OTHER MEASURES

MFCC

13 Mel-frequency cepstral coefficients (MFCC) are extracted after the non-linear compression of amplitude spectrum into 25 Mel-frequency bands. Short-term features were extracted with a 25-ms. hanning 5-ms. shifting window.

Spectral Flatness Measure

The spectral flatness measure (SFM) has been introduced as a measure of the noisiness contained in a signal [START_REF] Johnston | Transform Coding of Audio Signals using Perceptual Noise Criteria[END_REF][START_REF] Dubnov | Generalization of Spectral Flatness Measure for Non-Gaussian Linear Processes[END_REF]. The spectral flatness is defined as the ratio of the geometric mean to the arithmetic mean of the power spectrum :

SFM (i) = N (i) n=1 |A(n) 2 | 1/N (i) 1 N (i) N (i) n=1 |A(n)| 2 (5)
where A(n) is the amplitude of the n-th frequency bin in the considered frequency band.

Hence, SFM tends to zero when the spectral distribution of the frequency band exhibits a salient peak, and is equal to one when the spectral distribution of the frequency band is flat. The spectral flatness is usually referred to and can also be interpreted as a Wiener entropy [START_REF] Wiener | The human use of human beings : Cybernetics and society, chapter Cybernetics in History[END_REF]. The current implementation is based on the MPEG-7 standard [START_REF]Multimedia content description interface -Part 4 : Audio[END_REF], in which the spectral flatness is computed in the following 4 frequency regions :

(250-500), (500-1000), (1000-2000), (2000-4000) Hz 1 .

Voiced/UnVoiced Measure

The soft voiced/unvoiced measure (VUV) [START_REF] Griffin | A New Model-Based Analysis/Synthesis System[END_REF][START_REF] Obin | Cries and Whispers -Classification of Vocal Effort in Expressive Speech[END_REF] is a measure of the degree of voicing (alternatively, noisiness) contained in a signal. For each frequency band, the VUV is measured as :

VUV (i) = K (i) k=1 |A H (k)| 2 N (i) n=1 |A(n)| 2 (6)
where i denotes the i-th Mel frequency band, A H (k) the amplitude of the k-th harmonic, K the number of harmonics, and A(n) the amplitude of the n-th frequency bin in the i-th frequency band. Here, the harmonic/noise decomposition is obtained using the sinusoidal peak classification method presented in [START_REF] Zivanovic | Adaptive Threshold Determination for Spectral Peak Classification[END_REF].

Hence, VUV is equal to zero when no harmonic content is present in the frequency band, and to one when only harmonic content is present in the frequency band. In this study, the VUV has been computed over 25 Mel-frequency bands.

SPEECH DATABASE

Speech recordings of a video game consist of the interpretation of script lines by professional actors ; they are directed by an artistic director, whose role is to control the 1. Contrary to the other measures, which are all computed over 25 Mel frequency bands. expressive content of speech, depending on the place of the script within the overall scenario.Script lines may vary from a single sigh to a complete sentence. In role-playing games, the recording covers ten thousands of speech files that are split into hundreds of roles. The video game used for the study includes around 20,000 French (MASS EFFECT) and 40,000 German (DRAGON AGE) speech recordings, and around 500 roles (from a single to hundreds of recordings) for each video game. The duration of speech recordings varies from 0.1 seconds to 20 seconds with a mean duration of 2.5 seconds. Recordings were made in mono 48 kHz/16-24 bits uncompressed format.

Speech recordings are produced in a studio by professional actors with a varying distance and orientation to the microphone so as to compensate for the variations in acoustics due to changes in intended vocal effort (close while whispering, distant while shouting). Additionally, a sound engineer ensures that the speech level is constant through speech recordings so as to provide a homogeneous speech level through the video game. Hence, only information provided by changes in the source excitation or the vocal tract resonances can be used for the identification of changes in vocal effort. In particular, the degree and the extent of noisiness in speech may efficiently reflect significant changes in configuration and in intensity of the glottal source.

The identification of significant changes in vocal effort is critical in the production of video games for the application of specific settings that simulate the perception of proximity to the speaker by the player. For this purpose, the sound engineer is usually in charge for the manual classification of expressive speech recordings into three classes, which cover whis-

EVALUATION

The relevance of the noisiness measures for the classification of vocal effort into whispered/soft, normal, and loud/shouted speech has been conducted within a 5-fold cross-validation. Additional constraints on the design of the cross-validation have been adopted : well-balanced distribution of the vocal effort classes within the train and test sets ; no role overlapping across train and test sets, in order to prevent the system to be biased by speaker identification.

The classification system is based on the GMM-UBM/SVM system [START_REF] Charbuillet | GMM-Supervector for Content based Music Similarity[END_REF], which is a standard for speech recognition [START_REF] Reynolds | Speaker Verification Using Adapted Gaussian Mixture Models[END_REF][START_REF] William | Support Vector Machines using GMM Supervectors for Speaker Verification[END_REF]. A UNIVERSAL BACKGROUND MODEL (GMM-UBM) is used to model the acoustic variability in the speech database with a Gaussian Mixture Model (GMM), represented by a sequence of short-term acoustic feature vector (here, MFCCs and noisiness measure). Then, each utterance is represented as a supervector by MAP adaptation of the GMM-UBM mean vectors [START_REF] Reynolds | Speaker Verification Using Adapted Gaussian Mixture Models[END_REF]. Then, supervectors are used to determine the parameters of a SUPPORT VECTOR MACHINE classifier (SVM) which maximize the margin of a high-dimensional separation hyperplane for the classification [START_REF] William | Support Vector Machines using GMM Supervectors for Speaker Verification[END_REF].

During the training, each feature set is considered as a separate stream for the determination of the GMM-UBM and the SVM parameters. 64 GMMS with diagonal covariance matrices have been used to determine the parameters of the GMM-UBM, and a SVM with a GMM-supervector radial basis function (RBF) kernel has been determined with various values of the radial bandwidth (from 0.1 to 5). During the classification, the decision is made by fusioning the affinity obtained for each stream using average decision fusion. The performance of the system has been measured with the F-measure metric. Finally, the performance of the system corresponds to the optimal performance obtained for each feature set.

DISCUSSION

Table 1 summarizes the performance of the system for the noisiness measures considered, and in particular for a large range of α values in the R ÉNYI ENTROPY. The performance obtained leads to the following observations : First, the performance tendencies are strictly similar regardless to the language of the speech database, which strongly indicates that the acoustic configurations involved in a change in vocal effort may be universal -i.e., does not depend on a specific language.

Second, the use of a noisiness representation complementary to the standard MFCCS improves the performance regardless to the noisiness measure, which confirms the relevance of noisiness measures for speech recognition. More interestingly, a comparison of the existing noisiness measures suggests the following relevance rank : 1) VUV, 2) SFM, and 3) SHANNON ENTROPY, without a significant difference for the 2 last measures.

Finally, the R ÉNYI ENTROPY outperforms all of the other noisiness measures. The increase in performance is particularly significant for a small α (focus on the noise content) and for noisy speech (whispered), while a large α (focus on the harmonic content) does not provide any improvement -and may even degrade the performance of the system compared to the SHANNON ENTROPY. In all cases, the optimal performance is obtained with a α close to 0 (α = 0.01) and represents around a 10% relative error reduction over conventional MFCCS.

CONCLUSION

In this paper, the Rényi entropy was introduced as a generalization of the Shannon entropy to measure the degree of noisiness in audio signals, complementary to the standard MFCCs for audio and speech recognition. In audio signal representation, Rényi entropy presents the advantage of focusing either on the harmonic content (prominent amplitude within a distribution) or on the noise content (equal distribution of amplitudes). The proposed representation outperforms all other noisiness measures -including Shannon and Wiener entropies -in the large-scale classification of vocal effort in the real scenario of video games production of multi-language massive role-playing video games. This confirms the role of noisiness for speech recognition, and will further be extended to the classification of voice quality for the design of a automatic voice casting system in video games.

Fig. 1 .

 1 Fig. 1. An example of D L vector, see equation (3) : here, N part = 5, R part = 2 and L = 1/4 so that R noise = 8.

Fig. 2 .

 2 Fig.2. Rényi evaluations of the D L vectors with varying α, N part = 5 and R part = 2 ; the entropy values rise differently as L increases, depending on α : this shows that the impact of the noise level on the entropy evaluation depends on the entropy order.

Fig. 3 .

 3 Fig. 3. Study cases of Rényi entropy measures for whispered (top) and shouted (bottom) speech. From left to right : spectrogram, α = 0.001, α = 1 (Shannon entropy), and α = 3.

Table 1 .

 1 F-measure obtained for the conventional MFCC, MFCC + noisiness measures : (VUV), and MFCC + ENTROPY measures (SFM, SHANNON, R ÉNYI) for the MASS EFFECT (FR) and DRAGON AGE (GR) role-playing video games. pered/soft, normal, and loud/shouted speech. In the present study, whispered/soft speech covers sighs, true whisper, stage whisper, stressed whisper (tense whisper typically produced in a life-survival situation in which the conversation intimacy is absolutely required), soft speech, and any situation of intimacy in the speech communication. Loud/shouted speech includes orders, public announcements, exclamations, interjections, stressed-speech, and screams.

	MASS EFFECT	WHISPERED	NORMAL	SHOUTED	TOTAL	DRAGON AGE	WHISPERED	NORMAL	SHOUTED	TOTAL
	FRENCH						GERMAN
	MFCC		69.4	82.5	91.0	81.1	MFCC		73.1	77.2	87.1	79.0
	MFCC + SFM	73.1	84.4	92.6	83.3	MFCC + SFM	73.4	77.9	87.5	79.6
	MFCC + VUV	75.0	84.3	91.2	83.5	MFCC + VUV	74.3	78.7	87.2	80.1
	ENTROPY						ENTROPY
	MFCC + α						MFCC + α
	α = 0.001		75.0	84.0	91.3	83.4	α = 0.001		74.6	78.0	87.2	79.9
	α = 0.01		75.2	84.2	92.0	83.8	α = 0.01		75.1	78.5	87.5	80.4
	α = 0.1		75.0	84.3	91.3	83.5	α = 0.1		74.5	78.0	87.5	80.1
	α = 0.2		74.6	84.0	91.6	83.4	α = 0.2		74.5	78.2	87.3	80.0
	α = 0.4		74.5	84.0	91.5	83.4	α = 0.4		74.2	78.0	87.3	79.8
	α = 0.6		74.2	84.0	91.3	83.2	α = 0.6		74.0	77.9	87.0	79.6
	α = 0.8		74.2	84.0	91.2	83.0	α = 0.8		74.0	77.7	87.0	79.6
	α = 1	(SHANNON) 74.2	83.9	91.0	83.0	α = 1	(SHANNON) 73.8	77.5	87.1	79.5
	α = 2		75.0	84.3	91.3	83.5	α = 2		73.6	77.8	87.4	79.6
	α = 3		74.5	84.0	91.5	83.3	α = 3		72.8	77.0	87.4	79.1
	α = 4		74.6	83.8	91.5	83.2	α = 4		72.5	77.1	86.7	78.8
	α = 5		74.1	83.8	91.2	83.0	α = 5		72.4	77.0	86.5	78.5


Marie-Pierre Béal

Jean-Marc Champarnaud

Jean-Philippe Dubernard

Hadrien Jeanne

Sylvain Lombardy

Decidability of geometricity of regular languages ⋆

Geometrical languages generalize languages introduced to model temporal validation of real-time softwares. We prove that it is decidable whether a regular language is geometrical. This result was previously known for binary languages.

Introduction

A geometrical figure of dimension d is a connected set of sites in the lattice of dimension d which is oriented in the following sense: it has an origin O such that for any site P of the figure, there is a directed path with positive elementary step from O to P , a positive elementary step incrementing exactly one coordinate by 1. Finite geometrical figures are called animals [START_REF] Golomb | Puzzles, patterns, problems, and packings, With diagrams by Warren Lushbaugh[END_REF].

A geometrical language is the set of finite words over a d-ary alphabet whose corresponding Parikh points are the sites of a geometrical figure. It is called the geometrical language of the figure. Geometrical languages were introduced by Blanpain et al. in [START_REF] Blanpain | Geometrical languages[END_REF] and have applications to the modeling of real-time task systems on multiprocessors (see [START_REF] Geniet | WCET free time analysis of hard real-time systems on multiprocessors: a regular language-based model[END_REF], [START_REF] Blanpain | Geometrical languages[END_REF]). The definition of geometrical figures implies that all geometrical languages are prefix-closed (i.e. the prefix of any word of the language also belongs to the language).

Conversely, for any language of finite words over a d-ary alphabet, one can associate a set of sites corresponding to the Parikh points of the words of the language, the i-th coordinate of the Parikh point of a word counting the number of letters a i contained in the word. If the language is prefix-closed, the figure that it defines is geometrical. It turns out that a prefix-closed language is always contained in the language of its geometrical figure but this inclusion may be strict, the geometrical languages being exactly the languages satisfying this property.

Studying properties of a geometrical language may help to obtain properties of its geometrical figure and get information on the task systems that it models.

It is also interesting from the language theory point of view. A main subclass of these languages is the one of regular geometrical languages. From this point of view, geometricity is a strong property which can be weakened. The class of semi-geometrical languages contains languages such that any two words with the same Parikh image define the same left residuals.

We consider the class of regular languages and address the algorithmic problem of checking whether a regular language is geometrical (or semi-geometrical). It is already known from [START_REF]Geometricity of binary regular languages[END_REF] that it is decidable in polynomial time whether a regular binary language is geometrical. If n is the number of states of the minimal deterministic automaton accepting the language, an O(n 3 )-time algorithm is obtained for extensible binary languages in [START_REF] Champarnaud | An efficient algorithm to test whether a binary and prolongeable regular language is geometrical[END_REF], while an O(n 4 )-time algorithm works for all binary languages in [START_REF]Geometricity of binary regular languages[END_REF]. Two-dimensional geometry is used to prove the correctness of these algorithms. For alphabets in higher dimension, a non-polynomial algorithm has been obtained in the case where the minimal automaton of the language has one strongly connected component [START_REF] Champarnaud | Geometrical regular languages and linear diophantine equations[END_REF]. An exponential algorithm in [START_REF] Blanpain | Geometrical languages[END_REF] reduces the decidability of geometricity of a regular language to solving a system of Diophantine equations. Nevertheless, the system may be not linear in the general case and solving such a system is known to be undecidable.

In this paper, we give a decision scheme for all regular languages. The algorithm is nevertheless exponential and the existence of a polynomial algorithm to decide the geometricity of a ternary regular language for instance is still open. The problem may be NP-complete but this question is not addressed in the paper. Our solution uses only elementary automata theory and classical semilinear set theory to reduce the problem to a system of linear Diophantine equations. For binary alphabet, we show that a polynomial-time algorithm may be derived from the general solution. The algorithm is simpler that the O(n 4 )-algorithm obtained in [START_REF]Geometricity of binary regular languages[END_REF] but it has a worst-case time complexity of O(n 6 ).

The paper is organized as follows. The second section recalls the definitions and main properties of geometrical languages. Section 3 recalls some semilinear set theory [START_REF] Reutenauer | Aspects mathématiques des réseaux de Petri[END_REF] useful for Section 4, where the decision procedures are exposed.

Geometrical languages

Let d be a positive integer representing a dimension. Let x = (x 1 , . . , x d ), y = (y 1 , . . , y d ) be two points in N d , we say that x ≺ i y (or simply x ≺ y) if there is exactly one dimension index 1 ≤ i ≤ d such that x i + 1 = y i and x j = y j for j = i.

Let x, y be two points in N d . We call a directed path from x to y a finite sequence of points (z (i) ) 0≤i≤k contained in N d such that z (0) = x, z (k) = y, and

z (i) ≺ z (i+1) for 0 ≤ i ≤ k -1.
A geometrical figure is either the empty set or a set of points in N d containing the null point (0, . . , 0) and such that there is a directed path consisting of points belonging to the figure from the null point to any point of the set. Equivalently, for any nonnull point y in a nonempty geometrical figure, there is a point x in the figure such that x ≺ y.

Let A = {a 1 , . . , a d } be a finite alphabet of cardinal d. The set of words on the alphabet A is denoted by A * . The Parikh point associated to a word w of A * is the point (x 1 , . . , x d ) in N d such that x i is the number of occurrences of the letter a i in w.

A language L over A is a subset of A * . We say that a language is prefix-closed if any prefix of a word of the language belongs to the language.

The geometrical figure associated to a language L, denoted fig(L), is the set of Parikh points associated to the set of all prefixes of words of L. Conversely, the language associated to a geometrical figure F , denoted lang(F ), is the set of words whose Parikh points belong to the figure. It is a prefix-closed set.

Let L be a prefix-closed language. We say that L is a geometrical language if L is the language associated to some geometrical figure. By extension, if L is not prefix-closed, it is geometrical if the set of its prefixes is geometrical. Hence we shall only consider prefix-closed languages.

If F is a geometrical figure, we have

F = fig(lang(F )). If L is a prefix-closed language, we have L ⊆ lang(fig(L)
) but the converse is not true as is shown in the example below.

Example 1. Let L 1 be the language {aabbb, aabba, bbaaa, bbaab}. The set of prefixes of L 1 is a geometrical language in dimension 2 whose geometrical figure F 1 is pictured in Figure 1. The figure contains the points (0, 0), (0, 1), (0, 2), (1, 0), (2, 0), (2, 1), (1, 2), (2, 2), (2, 3) and [START_REF] Champarnaud | Geometrical regular languages and linear diophantine equations[END_REF][START_REF] Blanpain | Geometrical languages[END_REF].

Let now L 2 be the language {ab, b}. The set of its prefixes is {ε, a, ab, b}. It is not geometrical. Indeed the geometrical figure F 2 associated to L 2 contains the points (0, 0), (0, 1), (1, 0), [START_REF] Benois | On the complexity of some extended word problems defined by cancellation rules[END_REF][START_REF] Benois | On the complexity of some extended word problems defined by cancellation rules[END_REF]. Thus the language associated to F 2 contains the word ba which is not a prefix of a word in L 2 . Proof. If L is prefix-closed and geometrical, then there is a geometrical figure F such that L = lang(F ). We get lang(fig

(L)) = lang(fig(lang(F ))) = lang(F ) = L. Conversely, if L = lang(fig(L))
, it is a geometrical language by definition.

In [START_REF] Champarnaud | An efficient algorithm to test whether a binary and prolongeable regular language is geometrical[END_REF] is introduced the notion of semi-geometricity as follows. If u is a word and L a language, u -1 L denotes the set of words w such that uw belongs to L. A prefix-closed language L is said semi-geometrical if u -1 L = v -1 L for any two words u, v of L having the same Parikh point. It is proved in [START_REF] Champarnaud | An efficient algorithm to test whether a binary and prolongeable regular language is geometrical[END_REF] that a geometrical language is semi-geometrical but the converse is false.

Proposition 2 ([4]

). A prefix-closed language which is geometrical is semigeometrical.

Proof. Suppose that L = lang(F ) for some geometrical figure F . Let u, v ∈ L having the same Parikh point. Let w be a word such that uw ∈ L. Then the Parikh point associated to uw belongs to F and the Parikh point associated to any prefix of vw belongs to F . Since L = lang(F ), L contains the word vw.

Hence u -1 L ⊆ v -1 L and thus u -1 L = v -1 L.
A characterization of the geometricity of prefix-closed languages was obtained in [START_REF] Champarnaud | An efficient algorithm to test whether a binary and prolongeable regular language is geometrical[END_REF] as follows.

Proposition 3 ([4]

). A prefix-closed language L over A = {a 1 , . . , a d } is geometrical if and only if (ua i ) -1 L = (va j ) -1 L for any words u, v in L and letters a i , a j such that ua i and va j have the same Parikh point.

Proof. Suppose that L = lang(F ) is geometrical and w a word such that ua i w ∈ L. Hence the Parikh point associated to any prefix of ua i w belongs to F . Since the ua i and va j have the same Parikh point and u, v ∈ L, the Parikh point associated to any prefix of va j belongs to F . It follows that the Parikh point associated to any prefix of va j w belongs to F . As L = lang(F ), it contains the word va j w. Hence ua i w ∈ L if and only if va j w ∈ L.

Conversely, let us assume that, for any word w, any words u, v ∈ L, any indexes i, j, we have ua i w ∈ L if and only if ua j w ∈ L. Let F = fig(L). Let s = s 1 • • • s n be a word of length n such that the Parikh point of any prefix of s belongs to F . Let us show that s belongs to L. Since the Parikh point of s 1 belongs to F , we have s 1 belongs to L. Let us assume that the prefix

s 1 • • • s k of s belongs to L. As the Parikh point x of s 1 • • • s k s k+1 belongs to F and since F = fig(L), we get that x is the Parikh point of a word t = t 1 • • • t k t k+1 in L. Set u = t 1 • • • t k , a i = t k+1 , v = s 1 • • • s k , a j = s k+1 . Since ua i ∈ L, we get va j ∈ L and thus s 1 • • • s k s k+1 belongs to L.
By recurrence, we obtain that s belongs to L.

Note that the proof also shows that L is geometrical if ua i ∈ L if and only if va j ∈ L for any words u, v in L such that ua i and va j have the same Parikh point.

In this section, we present some definitions and known results about semilinear sets that will be useful in Section 4. We recall some results from [START_REF] Ginsburg | Bounded ALGOL-like languages[END_REF] and [START_REF] Eilenberg | Rational sets in commutative monoids[END_REF] about rational sets of commutative monoids (see for instance [12, 3.3]) or [13, 7.4], [START_REF]Elements of Automata Theory[END_REF]), and also [START_REF] Zur Gathen | Modern Computer Algebra[END_REF], [START_REF] Fischer | Super-exponential complexity of Presburger arithmetic[END_REF], [START_REF] Huynh | The complexity of semilinear sets, in Automata, languages and programming[END_REF] for complexity results).

Let (M, +) be a commutative monoid. A linear set of M is a set of the form u + V ⊕ , where u ∈ M , V is a finite subset of M and V ⊕ is the submonoid generated by V , i.e. the set of linear combinations over N of elements in V . Hence, if V = {v 1 , . . , v n }, a linear set is a set of the form

{u + x 1 v 1 + • • • + x n v n | x i ∈ N, v i ∈ V }.
A semilinear set is a finite union of linear sets, hence of the form r i=1

(u i + V ⊕ i ).
The set of rational subsets of M contains the finite parts and is closed by the operations union, +, and ⊕. It is known that the rational subsets of M are exactly its semilinear sets. Furthermore, the construction of a semilinear expression from a rational expression is effective.

We will consider the case where (M, +) is (Z d , +). Checking whether a semilinear set of Z d is empty or not is known to be decidable. It can be first reduced to the problem of checking whether a linear set is empty or not, which is decidable and NP-complete. A proof of the following Proposition can be found for instance in [START_REF] Reutenauer | Aspects mathématiques des réseaux de Petri[END_REF]Lemma 3.10] or in [START_REF] Sakarovitch | Éléments de théorie des automates[END_REF]Proposition 7.17].

Proposition 5. It is decidable whether the equation

x 1 u 1 + • • • + x k u k = c, where u i , c ∈ Z d , has a solution in N k .
In [START_REF] Gathen | A bound on solutions of linear integer equalities and inequalities[END_REF] is proved that, if a solution exists, then there is one with coefficients bounded above by (k + 1)M 1 , where M 1 is the maximum of the absolute values of all sub-determinants of a d × (k + 1) matrix made of the coefficients of u i and c.

Regular geometrical languages

In this section, we address the problem of checking whether a regular language is geometrical. We do not make any restrictions on the dimension or on properties of the regular language or on its minimal deterministic automaton.

We consider a regular prefix-closed language L on the alphabet A = {a 1 , . . , a d }.

It is accepted by a unique minimal finite complete deterministic automaton A = (Q, E, q 0 , T ), where Q is the set of states and E the set of edges. The unique initial state is q 0 and the set of final states is T . If L is the full language, we have Q = F = {q 0 }. Otherwise, Q has a non final sink state q s and all states but q s are final since L is prefix-closed. We denote by δ(q, u) the state ending the unique path labeled u starting at q.

By definition of the semi-geometricity, we get from Proposition 2 the following characterization of semi-geometrical regular prefix-closed languages.

Proposition 6 ([4]

). A regular prefix-closed language L is semi-geometrical if and only if δ(q 0 , u) = δ(q 0 , v) for any two words u, v of L having the same Parikh point.

It also follows directly from Proposition 3 the following characterization of geometrical regular prefix-closed languages.

Proposition 7 ([4]

). A regular prefix-closed language L is geometrical if and only if δ(q 0 , ua i ) = δ(q 0 , va j ) for any words u, v in L such that ua i and va j have the same Parikh point.

The main result of the paper is the following. Proposition 8. It is decidable whether a regular prefix-closed language is geometrical (resp. semi-geometrical).

Proof. Let A = (Q, E, q 0 , T ) be the minimal deterministic complete automaton accepting the language L. We consider the automaton B = (Q×Q, E ′ , (q 0 , q 0 ), T × T ) labeled on Z d , where the edges are defined as follows. There is an edge (p, q) (0,.., -----------→ (p ′ , q ′ ) with +1 positioned at the index i and -1 at the index j, whenever there are two edges in A p ai -→ p ′ and q aj -→ q ′ .

There is an edge (p, q) (0,..,0)

----→ (p ′ , q ′ ) whenever there are two edges in A

p ai -→ p ′ and q ai -→ q ′ .
The automaton B accepts a regular set of Z d . By construction, there is a path in B from (q 0 , q 0 ) to (p, q) labeled by the null vector of Z d if and only if there are two words u, v with the same Parikh point such that δ(q 0 , u) = p and δ(q 0 , v) = q. Let B (p,q) denote the regular subset of Z d of labels of paths of B from (q 0 , q 0 ) to (p, q). Thus checking whether L is semi-geometrical consists in checking whether there exists no pair of states (p, q) with p = q and p, q final, such that B (p,q) contains the null vector.

Similarly, there is a path in B from (q 0 , q 0 ) to (p, q) labeled by the Z d -vector x (i,j) = (0, . . , 0, -1, 0, . . , 0, +1, 0, . . , 0) (with -1 positioned at the index i and +1 at the index j) if and only if there are two words u, v such that δ(q 0 , u) = p and δ(q 0 , v) = q, and such that ua i and va j have the same Parikh point. Thus checking whether L is geometrical consists in checking whether, when B (p,q) contains x (i,j) for some pair of states (p, q) with p = q and p, q final, we have δ(p, a i ) = δ(q, a j ).

As a consequence both geometricity and semi-geometricity can be reduced to check whether the regular language B (p,q) of Z d contains a given point of Z d . If we find such a language B (p,q) containing x (i,j) , we check whether δ(p, a i ) = δ(q, a j ) and conclude that L is not geometrical if this condition does not hold.

We know from Section 3 that any set B (p,q) is semilinear, and the effective construction of Proposition 5 can be performed a finite number of times to decide whether B (p,q) contains some vector x (i,j) . Thus both geometricity and semi-geometricity are decidable.

The time complexity of the algorithm is exponential. Indeed, the automaton A being given, the construction of B can be done in polynomial time. Finding a rational expression of a set B (p,q) is exponential (the size of the expression itself can be exponential). Finding a semi-linear expression from a rational expression is a polynomial step. Finally, solving a linear Diophantine equation is exponential.

Example 2. We consider again the language L 2 = {ab, b}. The set of its prefixes {ε, a, ab, b} is accepted by the minimal deterministic complete finite automaton A pictured in the left part of

(-1, 1) (0, 0) (0, 0) Fig. 2. The automaton A (on the left), where the final states are colored, accepting the set of prefixes of L2, and the automaton B (on the right). Only the final states of B are represented.

We now come to the particular case of a two-letter alphabet A = {a, b}. It is proved in [START_REF]Geometricity of binary regular languages[END_REF] that it is decidable in polynomial time whether a regular binary language is geometrical. An O(n 3 )-time algorithm is obtained for an extensible binary language in [START_REF] Champarnaud | An efficient algorithm to test whether a binary and prolongeable regular language is geometrical[END_REF], an O(n 4 )-time algorithm works for all binary languages in [START_REF]Geometricity of binary regular languages[END_REF]. We give below another polynomial-time algorithm for deciding the geometricity of binary regular languages which is based on the construction used in the proof of Proposition 8. It also uses an algorithm of [START_REF] Benois | On the complexity of some extended word problems defined by cancellation rules[END_REF] for computing the closure of an automaton under some rewriting rules. This algorithm has an O(n 6 ) time complexity which is worse than the complexity of the algorithm given in [START_REF]Geometricity of binary regular languages[END_REF], but it is simpler. Proposition 9. ( [START_REF]Geometricity of binary regular languages[END_REF]) It is decidable in polynomial time whether a regular prefixclosed language on a two letter alphabet is geometrical (resp. semi-geometrical).

Proof. Let A = (Q, E, q 0 , T ) be the n-state minimal deterministic complete automaton accepting the language L. We first construct an automaton B ′ over Z which plays the same role as the automaton B in the proof of Proposition 8 but has its labels in Z d-1 . Let B ′ = (Q × Q, E ′ , (q 0 , q 0 ), T × T ) labeled on Z. The edges of B ′ are defined as follows. There is in B ′ an edge

(p, q) +1 --→ (p ′ , q ′ ) if p a -→ p ′ and q b -→ q ′ are edges of A, (p, q) -1 --→ (p ′ , q ′ ) if p b -→ p ′ and q a -→ q ′ are edges of A, (p, q) 0 -→ (p ′ , q ′ ) if p ℓ -→ p ′ and q ℓ -→ q ′ are edges of A,
where ℓ = a or ℓ = b.

Let B ′ (p,q) denote the regular subset of Z of labels of paths of B ′ from (q 0 , q 0 ) to (p, q). There is a path in B ′ from (q 0 , q 0 ) to (p, q) labeled by -1 if and only if there are two words u, v such that δ(q 0 , u) = p and δ(q 0 , v) = q and such that ua i and va j have the same Parikh point. Thus checking whether L is geometrical consists in checking whether when B ′ (p,q) contains -1 for some pair of states (p, q) with p, q final, we have δ(p, a i ) = δ(q, a j ). Note that B ′ (p,q) contains -1 if and only if B ′ (q,p) contains 1. Adding an extra initial edge labeled 1 reduces the problem to checking whether B ′ (p,q) contains 0. The automaton B ′ is an n 2 -state non-deterministic automaton labeled in the subset X = {-1, 0, 1} of the group Z. By definition, the number of transitions of B ′ is at most 4n 2 . We say that the pair of consecutive edges of

B ′ s ℓ -→ t m -→ u, is reducible if ℓ + m ∈ X.
We construct an automaton C which is a closure of B ′ in the following sense. Whenever there is a reducible pair of consecutive edges of B ′ as above, we add in C the edge

s ℓ+m ---→ u.
This construction is an instance of the algorithm used in [START_REF] Benois | On the complexity of some extended word problems defined by cancellation rules[END_REF] for computing the set of descendants of a regular set for Thue systems of a certain type. The rewriting rules that we consider are given by pairs of words in X * × X * which are ((-1)1, 0), (1(-1), 0), (00, 0), (01, 1), (10, 1), ((-1)0, -1), (0(-1), -1).

The computation of the automaton C can be done as follows. We keep a queue of edges of C containing initially the edges of B ′ . For each edge e = s ℓ -→ t of this queue, we consider the edges f = t m -→ u following e and the edges g = u m -→ s preceding e, in order to check whether ef of f e is a reducible pair of edges. In that case, we add a new edge in the queue s

ℓ+m ---→ u (or u ℓ+m ---→ t).
The number of edges of C is at most 3n 4 and each edge is added and removed only once in the queue. Whenever an edge (s, ℓ, t) is removed, the edges going out of t and coming in s are checked. There are at most 6n 2 such edges. Thus the time complexity the algorithm is O(18n 6 ).

We claim that there is a path in B ′ from s to t labeled by 0 if and only if there is an edge in C from s to t labeled by 0. Indeed, by construction, if there is an edge in C from s to t labeled by 0, then there is a path in B ′ from s to t labeled by 0. Conversely, let

s ℓ1 -→ s 1 ℓ2 -→ . . ℓr -→ s r = t
be a path in B ′ labeled by 0 of minimal length. This path contains no consecutive reducible pair of edges as factor since otherwise we could get a shorter path labeled with the same label, origin and end. As a consequence the factors (-1)1, 1(-1), 01, 10, 0(-1), (-1)0, or 00, are forbidden in the sequence ℓ 1 . . ℓ r . This implies that all ℓ i are equal. Since ℓ 1 + • • • + ℓ r = 0, we get r = 1 and ℓ 1 = 0.

The algorithm can be implemented as follows. Let ℓ ∈ X. We set B ′ ℓ [s, t] = true if there is an edge (s, ℓ, t) in B ′ and B ′ ℓ [s, t] = false otherwise. We define the matrices C ℓ similarly.

A pseudocode for computing the matrices C ℓ from the matrices B ′ ℓ is given in the procedure Closure below. Example 3. We consider the language L 3 = {ab, ba} * . The set of its prefixes is accepted by the deterministic complete finite automaton A pictured in the left part of Figure 3. The automaton B ′ constructed in the proof of Proposition 9 is pictured in the right part of the figure. The closure automaton C of B ′ is pictured in Figure 4. Since C has no edge labeled by 0 from (1, 1) to either [START_REF] Blanpain | Geometrical languages[END_REF][START_REF] Champarnaud | Geometrical regular languages and linear diophantine equations[END_REF] or [START_REF] Champarnaud | Geometrical regular languages and linear diophantine equations[END_REF][START_REF] Blanpain | Geometrical languages[END_REF], the language L 3 is a geometrical language.

Fig. 1 .

 1 Fig. 1. The geometrical figures F1 (on the left) and F2 (on the right).

Proposition 4 .

 4 (see[START_REF] Reutenauer | Aspects mathématiques des réseaux de Petri[END_REF] Proposition 3.5]) Let M be a commutative monoid. A subset of M is rational if and only if it is semilinear.

Figure 2 .

 2 The automaton B constructed in the proof of Proposition 8 is pictured in the right part. We have B (2,3) = {(1, -1)}. It contains (1, -1) and δ(2, b) = δ(3, a). As a consequence L 2 is not geometrical. It is semi-geometrical since neither B (2,3) nor B (3,2) contains the null vector.

Closure

  (transition matrices B ′ ℓ ) 1 for all ℓ ∈ X 2 do C ℓ ← B ′ ℓ 3 edgeQueue ← theedges of B ′ 4 while edgeQueue is nonempty 5 do remove an edge s ℓ -→ t from edgeQueue 6 for all states u, all m such that l + m ∈ X, 7 do if C ℓ+m [s, u] = false 8 then C ℓ+m [s, u] ← true 9 add s ℓ+m ---→ u to edgeQueue 10 if C ℓ+m [u, t] = false 11 then C ℓ+m [u, t] ← true 12 add u ℓ+m ---→ t to edgeQueue 13

1 Fig. 3 .

 13 Fig. 3. The automaton A (on the left) accepting the set of prefixes of L3 = {ab, ba} * , and the automaton B ′ (on the right). Only the final states are represented.

Fig. 4 .

 4 Fig. 4. The automaton C which is the closure of the automaton B ′ .

⋆ This work is supported by the French National Agency (ANR) through "Programme d'Investissements d'Avenir" (Project ACRONYME n • ANR-10-LABX-58).


Marco Congedo

Ronald Phlypo

Jonas Chatel-Goldman

ORTHOGONAL AND NON-ORTHOGONAL JOINT BLIND SOURCE SEPARATION IN THE LEAST-SQUARES SENSE

Keywords: Joint Blind Source Separation, Hyperscanning, Brain Coupling, Synchronization

We present two new algorithms for the orthogonal and nonorthogonal joint blind source separation (JBSS), a flexible framework that extends the well-known blind source separation to the case when multiple datasets are decomposed simultaneously. The algorithms minimize the total sum of squares of the off-diagonal terms by means of very simple gradient ascent iterations.

INTRODUCTION

Blind Source Separation (BSS) is a well-known framework including Independent Component Analysis and other decomposition methods aiming at recovering source signals in MIMO systems [START_REF] Comon | Handbook of Blind source separation. Independent component analysis and applications[END_REF]. BSS nowadays encompasses a wide range of engineering applications such as speech enhancement, image processing, geophysical data analysis, wireless communication and biomedical signal analysis. Generally speaking, BSS takes as input a multivariate linearly mixed signal received over N sensors and outputs a P≤N multivariate demixed signal. More recently the joint blind source separation (JBSS) approach has been proposed in biomedical imaging [START_REF] Vía | Joint blind source separation from second-order statistics: Necessary and sufficient identifiability conditions[END_REF][START_REF] Li | Joint blind source separation by generalized joint diagonalization of cumulant matrices[END_REF][START_REF] Li | Joint blind source separation by multi-set canonical correlation analysis[END_REF][START_REF] Congedo | Approximate joint singular value decomposition of an asymmetric rectangular matrix set[END_REF]. Whenever M datasets are available and a relation exists among the sources of the M sets, this approach exploits the joint statistics of the M datasets by solving the M BSS problems simultaneously rather than independently. Several algorithms for performing JBSS in the case of orthogonal mixing matrices have been proposed [START_REF] Vía | Joint blind source separation from second-order statistics: Necessary and sufficient identifiability conditions[END_REF][START_REF] Li | Joint blind source separation by generalized joint diagonalization of cumulant matrices[END_REF][START_REF] Li | Joint blind source separation by multi-set canonical correlation analysis[END_REF][START_REF] Congedo | Approximate joint singular value decomposition of an asymmetric rectangular matrix set[END_REF]. In this paper we extend previous work performed on BSS [START_REF] Congedo | Approximate joint singular value decomposition of an asymmetric rectangular matrix set[END_REF][START_REF] Congedo | Least-squares joint diagonalization of a matrix set by a congruence transformation[END_REF][START_REF] Pham | Least square joint diagonalization of matrices under an intrinsic scale constraint[END_REF] and we describe a leastsquares gradient approach to JBSS allowing a simple solution for both the orthogonal and nonorthogonal case.

METHOD

Problem Statement

Suppose we are given M datasets, with m=1,…,M. As usual, we suppose that each data set is multidimensional, such as          

      , , , m k m m k m k t t t  x A s η (1.1)
where A m ℝ NxP is a (t, k)-invariant full column rank mixing matrix, s m,k (t) ℝ P , with P≤N, holds the source components over the t dimension and  m,k (t) ℝ N is spatially uncorrelated additive noise, assumed also uncorrelated with s m,k (t). Notice that the mixing matrix is specific to each dataset, but is the same for each dataset along the K observations. This model is an extension to multiple datasets of the typical model found in the BSS literature. It has been proposed already several times [START_REF] Vía | Joint blind source separation from second-order statistics: Necessary and sufficient identifiability conditions[END_REF][START_REF] Li | Joint blind source separation by generalized joint diagonalization of cumulant matrices[END_REF][START_REF] Li | Joint blind source separation by multi-set canonical correlation analysis[END_REF][START_REF] Congedo | Approximate joint singular value decomposition of an asymmetric rectangular matrix set[END_REF][START_REF] Anderson | Joint Blind Source Separation With Multivariate Gaussian Model: Algorithms and Performance Analysis[END_REF]. It reduces to the very common model used in BSS

      k k k t t t  x
As η when only one dataset is available. In JBSS we require to find the M matrices B m ℝ NxP , m=1,…,M, yielding the source estimates

    ,, T m k m m k tt  s B x
, where, under mild assumptions on the noise, the demixing matrices B m estimate the Moore-Penrose pseudo-inverse of the mixing matrices up to a sign, scale and permutation indeterminacy, as in the BSS case. However in JBSS we require the permutation be the same for all M datasets, otherwise the analysis of the corresponding sources in the M datasets becomes difficult. This is, among others, a key advantage of the JBSS approach. Notice that for the sake of simplicity we suppose hereafter that N=P, this quantity being the same across datasets.

The Joint Blind Source Separation (JBSS)

In order to apply JBSS we extract K[M(M+1)/2] matrices of second-order statistics from the K observations of M multivariate datasets [START_REF] Vía | Joint blind source separation from second-order statistics: Necessary and sufficient identifiability conditions[END_REF][START_REF] Congedo | Approximate joint singular value decomposition of an asymmetric rectangular matrix set[END_REF][START_REF] Anderson | Joint Blind Source Separation With Multivariate Gaussian Model: Algorithms and Performance Analysis[END_REF]. From Eq. (1.1) these matrices follow the theoretical model , , ,

T ij k i ij k j ij k  CA Λ A N , with i,j=1,…,M, (1.2)
where the  ij,k matrices, the unknown source statistics, are supposed all diagonal, surely non-null if i=j (auto-statistics within datasets) and possibly non-null even for i≠j (crossstatistics between corresponding sources of the i and j datasets). The matrices N ij,k are unknown noise matrices holding additive measurement noise and sample estimation errors. In order to estimate the M demixing matrices we seek matrices making all

K[M(M+1)/2] distinct products ,, T ij k i ij k j  Q B C B (1.3)
as diagonal as possible. This implies that the output (source) statistics within datasets are diagonalized (for i=j), as in the BSS framework. In addition, the output cross-statistics between datasets are also diagonalized, thus corresponding sources across datasets may be correlated. Notice that

C ij,k =C T ji,k , thus it suffices to consider K[M(M+1)/2]
products instead of all KM 2 products.

Least-Squares Functional

We want to find matrices B T m minimizing the sum of squares of the elements outside the diagonals of all

Q ij,k , that is   1 2 , ,..., ,, min M T i ij k j F i j k off  BB B C B ,
where the off operator nullifies the diagonal elements of the matrix argument. The overall strategy is to sequentially search for each matrix B i , for i=1,…,M and iterate such sequential search until convergence. Let us denote with B the set of all demixing matrices. In the sequel, following [START_REF] Li | Joint blind source separation by generalized joint diagonalization of cumulant matrices[END_REF], let us define the functional of interest for any given i=1,…,M as

    22 | , , 2 i off ij k ii k FF j i k k off off       BB QQ , (1.4)
wherein we have used Eq. (1.3) and we have separated the partitions for i≠j (firt Frobenius norm) and the partition for i=j (second Frobenius norm). Equation (1.4) can also be written such as

| | | | i i i i off tot diag tot diag         B B B B B B B B , (1.5)
where the "total" and "diagonal" parts are

    2 | , , , 2 i tot T ij k ij k ii k k j i tr tr         BB Q Q Q and (1.6)             22 | , , 2 i diag T T T T ij k ii k i n j n i n i n k j i n n           BB b C b b C b (1.7)
respectively. In Eq. (1.7), b i(n) is the n th column vector of B i , with n=1,…,N and b T i(n) its transpose.

The Orthogonal Mixing Matrices Case

In this case the exact estimation of B i is equal to A i up to permutation and scale indeterminacy, for all m=1,…,M and it is well known that the "total" function is invariant with respect to B. Thus we are left with the problem of maximizing iteratively the "diag" functional in (1.7), for i=1,…,M. Let us rewrite the objective function as

    2 2 | , , 2 i diag ij k ii k F F k j i j i diag diag           BB QQ ,
where the diag operator nullifies the off-diagonal elements of the matrix argument, and then as

    ,, | ,, 2 i n ij k n n ji k n diag j i n k n ii k n n ii k n n tr tr               BB E Q E E Q E E Q E E Q E ,
where matrix E n is the elementary matrix filled with entry 1 at position (n,n) and 0 elsewhere. The above function is a matrix polynomial of second degree in B i . The derivative is of first degree in B i for the first trace and of third degree in B i for the second trace. However, using the symmetry of matrices C ii,k , the gradient simplifies to

    ,, | ,, 4
4 i ij k j n n ji k n diag j i n k i ii k i n n ii k n n              BB C B E E Q E B C B E E Q E . Thus         | 11 4 ,..., i diag i i i N i N i      BB M b M b B , (1.8)
where

        ,, TT ij k ij k i n j n j n kj   M C b b C . (1.9)
In words, the gradient of the N vectors of B i should be taken as the eigenvectors of corresponding matrices M i(n) associated with their largest eigenvalue, for all n=1,…,N. In order to update these vectors we limit ourselves to a single power iteration [START_REF] Congedo | Least-squares joint diagonalization of a matrix set by a congruence transformation[END_REF][START_REF] Pham | Least square joint diagonalization of matrices under an intrinsic scale constraint[END_REF]. After updating all vectors of B i we need to orthogonalize B i so as to ensure that at each step B i stays in the orthogonal group [START_REF] Congedo | Approximate joint singular value decomposition of an asymmetric rectangular matrix set[END_REF]. Therefore, we have the following simple updating rule: for all i=1,…,M do

        11 ,..., i i i i N i N i orthogonalize         B M b M b B .
The iterative algorithm is summarized here below:

Note that in practice the orthogonalization is computed faster as B i ←UV T , where UΓV T is the SVD of B i [START_REF] Congedo | Approximate joint singular value decomposition of an asymmetric rectangular matrix set[END_REF].

The Non-Orthogonal Mixing Matrices Case

In this case the "total" function is not invariant to B, hence we need to explicitly minimize the "off" functional in (1.4). Furthermore we need to avoid the trivial solution B T m =0, for any m=1,…,M. Therefore, we minimize the "off" functional in (1.5)-(1.7) with a constraint (w.c.) on the norm of the column vectors of B m , such as

      | , w.c. 1, 1,..., i tot diag T i n i n i n nN      BB b M b , (1.10)
where matrices M i(n) are given in (1.9). Note that this is an "intrinsic" constraint, as proposed first in [START_REF] Congedo | Least-squares joint diagonalization of a matrix set by a congruence transformation[END_REF][START_REF] Pham | Least square joint diagonalization of matrices under an intrinsic scale constraint[END_REF]. We use the method of Lagrange multipliers to turn (1.10) into an unconstrained optimization problem. The method leads us to minimize

          2 | , , , 22 , , , , 2 44
i tot diag ij k ji k ij k k j i n ij k j n ji k n n ii k i n ii k n k j i n n L tr tr                    BB Q Q Q C B E Q E C B E Q E
where the Lagrangian multipliers δ n are adjusted in order to satisfy the constraint. Using again the symmetry of the matrices C ii,k and exploiting the previous results in (1.8), the gradient of the Lagrangian reads

      | | , , , ,
44 i i tot diag diag ij k j ij k ii k i ii k k j i i i L                 BB BB C B Q C B Q B B or           | 11 4 4 ,..., i tot diag ii i i i N i N i L       BB M B M b M b B , where     ,, TT i ij k j j ij k in k j n    M C B B C M ,
that is, the sum of matrices already found in (1.9). Setting the gradient to zero gives us a stationary point for our optimization, which for each B i is given by

M i B i =[M i(1) b i(1) ,…,M i(n) b i(n) ]
. This is a generalized eigenvalue-eigenvector problem, where each b i(n) is the eigenvector of M i(n) in the metric of M i . Again, limiting ourselves to one single power iteration per update step, this yields the simple updating rule:

For i=1,…,M do                     1 11 1/2
,..., for =1,..., do

ii i i i N i N T i n i n i n i n i n nN              B M M b M b b b b M b .
In practice, we sought to avoid the computation of the matrix inverse, therefore we proceed more efficiently, albeit equivalently, in the following way :

RESULTS

In this section the behavior of the proposed algorithms is assessed by means of simulations. Input matrices C ij,k are generated according to the model in Eq.(1.2); matrices  ij,k are generated as square diagonal matrices with each diagonal entry randomly distributed as a chi-squared with M degrees of freedom and divided by M; noise matrices N ij,k are symmetric and have entries randomly Gaussian distributed with zero mean and σ standard deviation (sd). The parameter σ controls the signal to noise ratio of the input matrices. Several different values of σ will be considered in the simulations. The mixing matrices A m , m=1,…,M, are generated as orthogonal or non-orthogonal. Orthogonal matrices are generated by first generating a matrix with entries randomly drawn from a Gaussian distribution with zero mean and sd=1 and then taking its left singular vector matrix. In this case the conditioning of the mixing matrices does not jeopardize the performance of the algorithms and we can evaluate their robustness with respect to noise. In order to generate non-orthogonal matrices, the matrices generated as above are perturbed by adding to each entry a number randomly drawn from a Gaussian distribution with zero mean and sd=1/2. In this case the mixing matrices have variable conditioning and we can Algorithm OJoB (Orthogonal Joint BSS) Initialize B 1 ,…,B M as orthogonal matrices (e.g., identity) Repeat For i=1,…,M do Compute the N matrices M i(n) using (1.9) For n=1,…,N

do b i(n) ←M i(n) b i(n) B i ← (B i T B i ) -1/2 B i Until Convergence
Algorithm NOJoB (Non-Orthogonal Joint BSS) Initialize B 1 ,…,B M so as to satisfy constraint in (1.10) Repeat For i=1,…,M do Get the N matrices M i(n) using (1.9) and their sum

M i Do Cholesky decomposition M i =LL T . For n=1,…,N do Solve Lx=M i(n) b i(n) for x and L T y=x for y b i(n) ←y(y T M i(n) y) -1/2 Until Convergence
evaluate the behavior of the algorithms with respect to the conditioning of the mixing matrices.

The algorithms estimate the demixing matrices B T 1 ,…,B T M , which should approximate the pseudo-inverse of actual mixing matrices A 1 ,…,A M up to row scaling (including sign) and global permutation. Then, matrices G m = B T m A m should approximate as much as possible a scaled permutation matrix [START_REF] Comon | Handbook of Blind source separation. Independent component analysis and applications[END_REF]. For each estimated demixing matrix we consider the Amari-like performance index [START_REF] Comon | Handbook of Blind source separation. Independent component analysis and applications[END_REF], which is computed as   where maxeig and mineig are the largest and smallest eigenvalue of the argument, respectively. Figure 1 shows the performance (1.11) obtained by the OJoB and NoJoB algorithms with orthogonal mixing (input) matrices, N=P=3 sensors/sources and several combinations of M (number of datasets), K (number of observations), and σ (noise level). One hundred simulations have been performed for each algorithm and for each combination of M, K and σ. Each dot represent the intersection of the performance obtained in one simulation when the algorithm is initialized with identity matrices (x-axis), that is, possibly far from the optimal solution, and with the exact solutions (y-axis). Dots lying on the 45° line indicate that the algorithms have a stable attractor, despite the added noise. Dots lying above the 45° line indicate that the algorithm gets far from the exact solution. These results show that for both algorithms the degradation engendered by noise is mitigated by increasing either K or M. Also, when either M or K are much larger than N no divergence of the algorithms is noticed. Overall, NoJoB appears more stable than OJoB.

Figure 2 shows the performance of the NoJoB algorithm (yaxis) vs. the mixing matrices conditioning (1.12) with nonorthogonal mixing (input) matrices, N=P=3 and several combinations of M, K, and σ. Results show that the more noise there is in the system the more the conditioning affects the performance. Furthermore, the degradation is not mitigated by increasing K and only moderately mitigated by increasing M.

CONCLUSION

We have presented two new algorithms performing JBSS in a least-squares framework. Preliminary results encourage further investigation. Before NoJoB, only one nonorthogonal JBSS algorithm has been proposed [START_REF] Anderson | Joint Blind Source Separation With Multivariate Gaussian Model: Algorithms and Performance Analysis[END_REF].

,

  where indexes x and y run over 1,…,N (rows and columns of matrices G m ), g m xy is the (x,y) entry of matrix G m , and |.| denotes the absolute value of the argument. We define the composite performance as a function of the geometric mean of the performance indexes obtained over the M matrices, such as of π above 2 indicate a very good performance. Note that the composite performance defined this way is dominated by the worst performance over the M performances. The higher the value of the composite index (1.11), the higher the performance. Likewise, the composite conditioning with respect to matrix inverse of the mixing matrices is defined as

Figure 1 .

 1 Figure 1. Composite performance of the OJoB (top row: a to d) and NOJoB (bottom row: e to h) algorithms (1.11) when initialized with the identity matrices (x-axis) vs. when initialized with the inverse of the actual mixing matrices (y-axis), for N=P=3, three noise levels (σ) and several combinations of M and K.

Figure 2 .

 2 Figure 2. Composite performance of the NOJoB algorithm (y-axis) vs. composite condition number (1.12) of mixing matrices. Same parameters as Fig. 1.

AKNOWLEDGEMENTS

This research has been partially funded by the Grenoble Institute of Technology with a BQR (Bonus Qualité Recherche) and by the ANR (Agence Nationale de la Recherche), through projects Gaze&EEG, RoBIK and OpenViBE2.


Thomas Palfray
email: thomas.palfray@univ-rouen.fr

Pierrick Tranouez
email: pierrick.tranouez@univ-rouen.fr

David Hébert
email: david.hebert@univ-rouen.fr

Thierry Paquet
email: thierry.paquet@univ-rouen.fr

Stéphane Nicolas
email: stephane.nicolas@univ-rouen.fr

Logical segmentation for article extraction in digitized old newspapers

Keywords: I.7.5 [Document and Text Processing]: Document Capture -Document analysis Algorithms page layout analysis, information extraction from document images, logical structure, articles extraction in newspapers, document image labelling, conditional random field, structural analysis

Newspapers are documents made of news item and informative articles. They are not meant to be red iteratively: the reader can pick his items in any order he fancies. Ignoring this structural property, most digitized newspaper archives only offer access by issue or at best by page to their content.

We have built a digitization workflow that automatically extracts newspaper articles from images, which allows indexing and retrieval of information at the article level. Our back-end system extracts the logical structure of the page to produce the informative units: the articles. Each image is labelled at the pixel level, through a machine learning based method, then the page logical structure is constructed up from there by the detection of structuring entities such as horizontal and vertical separators, titles and text lines. This logical structure is stored in a METS wrapper associated to the ALTO file produced by the system including the OCRed text. Our front-end system provides a web high definition visualisation of images, textual indexing and retrieval facilities, searching and reading at the article level. Articles transcriptions can be collaboratively corrected, which as a consequence allows for better indexing.

We are currently testing our system on the archives of the Journal de Rouen, one of France eldest local newspaper. These 250 years of publication amount to 300 000 pages of very variable image quality and layout complexity. Test year 1808 can be consulted at plair.univ-rouen.fr.

INTRODUCTION

During the last twenty years, the archives and national libraries of the whole world implemented many programmes of digitalization of their patrimonial funds in order to preserve them while facilitating the access of the public to information they contain. The case of old newspapers is emblematic of this will of historical dissemination of information, because of the wealth and the diversity of the contained information in the documents of this type. Nevertheless, these documents require particular treatments to fully exploit their informational contents, because of their size, of their particularly complex page layout and its evolution with the technical innovations of printing works,. Moreover, the quality of conservation of this kind of document is often variable depending on the historical periods because of the important variations of quality of paper used, resulting sometimes in a very degraded digitized copy, even unusable. In order to exploit these documents as well as possible, it is necessary to have a segmentation in articles making it possible to isolate the interesting parts of a newspaper for an easier consultation by the user, by the means of modern digital tools. Having in mind these difficulties, we developed a new method for logical labelling of old newspapers. This method is intended to extract metadata in the images of the digitized newspapers, thanks to the joint use of a method of classification of sequence of pixels based on conditional random field modelling, associated with a set of rules defining the concept of article within a newspaper. In a first time we describe the previous work related to this task in the literature, then we fully describe the method we propose before presenting the results obtained on newspaper issues from "Journal de Rouen", a regional French newspaper. Finally we describe briefly the complete process in which this method is integrated, and then we conclude by a discussion about the potential of the method and future work.

Related work

Since 2001 is organised in the context of the ICDAR Conference, a document page segmentation competition [START_REF] Antonacopoulos | ICDAR 2009 Page Segmentation Competition[END_REF] in which some of the proposed algorithms may have goals similar to the system we propose in this paper. Nevertheless, the document dataset used for this competition contains only modern documents; therefore the proposed methods may be inefficient for old newspapers. We can cite however the work described in [START_REF] Yin | Document Segmentation Using Pixel-Accurate Ground Truth[END_REF] which exploits a method of labelling at pixel level adaptable to this type of documents. [START_REF] Breuel | Two geometric algorithms for layout analysis[END_REF] describes an approach based on the determination of the maximal empty rectangles to delimit columns and text blocks. This method is integrated in the system OCROPUS. Although interesting, this method does not allow for difficulties inherent to old documents (skewing, deformations,...). A more interesting method taking into account these difficulties is described in [START_REF] Lemaitre | Approche perceptive pour la reconnaissance de filets bruités, Application à la structuration de pages de journaux[END_REF]. The authors propose to use a multiscale approach to extract text blocks in old newspapers. This method seems to be efficient, but as the previous one, only the segmentation in text blocks is provided, but no logical reading order, what is important to determine the logical structure of articles. The approach we propose in this paper tries to bring a solution to this problem.

Proposed approach

Binary images of the digitized newspaper issues are considered at the input of the system, and files in METS format are produced at the output. The METS files contain the structuration of the newspaper issues in articles, and the ordering of the articles according to the reading order. To do that we want to identify the editorial model of the document using visual clues determined thanks to a conditional random field model associated to a structural analysis using a recursive algorithm. The distinctive steps of the proposed method are the following ones:

• logical labelling at pixel level using conditional random field modelling • smoothing of the labelling using majority vote • extraction of the text lines • generation of a segmentation mask using identified rulers • recursive analysis of the document page to extract articles and determine the reading order

Logical labelling at pixel level

The proposed method for article extraction in newspaper document images relies on a segmentation stage using an analysis of the document image by a particular conditional random field (CRF) model with multi-scale quantization feature functions. This system provides a fine segmentation at pixel level, where each pixel is associated to a logical label specifying the logical function of the entity this pixel belongs to. The segmentation obtained thus does not consist only of one division in physical blocks but it also brings a logical identification to the detected entities. See [5] for more details about this model. This segmentation considers ten logical labels describing precisely the physical organisation of the textual content, and particularly the inter and intra character spacing. These ten labels are finally grouped into six informative labels for the logical labelling into articles or article parts:

• vertical separator • horizontal separator
• title (compound by the labels "title character", "title inter-character" and "title inter-word")

• text line (compound by the labels "character", "intercharacter" and "inter-word")

• noise

• background

Each image is analysed line by line at the pixel level, and the labelling results of all the lines are concatenated to produce a labelled image noted 𝐼𝑠𝑒𝑔, which is then exploited by the next analysis stages. An example of labelling obtained at this stage is shown on Figure 1b. At the end of this stage we dispose of a set of elements identifying the vertical and horizontal separators, the titles, and the text lines. However these elements are locally detected and they might be fragmented or erroneous. A complementary analysis using grouping rules defined by a simple and generic layout model is then applied to analyse the spatial placing of these entities and thus allow to the extract the articles.

Post processing for the logical extraction of the articles

Labelling smoothing using majority vote

Despite the ability of the CRF model to label each region or pixel according to the underlying layout model, some labelling error may appear. For this reason we apply a first algorithm to smooth the labelling result by applying a majority vote on the labels associated to the black pixels of the binary image (which correspond to the informative pixels by comparison with the white ones which correspond generally to the background), as described by algorithm1. The results provided by this smoothing algorithm are shown on figure 1c.

Algorithm 1: majority vote on connected components input: 𝐼𝑠𝑒𝑔, image resulting of the segmentation output: 𝐼𝑒𝑛𝑡𝑖𝑡𝑦, image with the extracted entity Extract in 𝐼𝑠𝑒𝑔 the connected components constituted by all the connected labels except those of the "background" label; For all the connected components CC do ⎣ 𝑛𝐸𝑖 ← the number of pixels labelled 𝐸𝑖; Affect to all the pixels of CC, the label 𝑎𝑟𝑔𝑚𝑎𝑥 !" (𝑛𝐸𝑖)

Once the image 𝐼𝑒𝑛𝑡𝑖𝑡𝑦 is entirely built, we can extract the text lines and the articles.

Text line extraction

The text lines are obtained by extracting the connected components, which are labelled "text" in the resulting image 𝐼𝑐𝑐.

In spite of the robustness of our extraction method, some text lines may be connected because of important deformation in the image due to document degradations or digitization artefacts. To solve this problem we try to detect the connected text lines by calculating the mean surface of the text lines, contained in a newspaper issue. We pose the assumption that the text lines, whose convex hulls delimit a surface much higher than the mean surface, are certainly erroneous. These text lines are then corrected by a specific algorithm, which allows separating them, before being associated to the article blocks extracted using our segmentation method

Article extraction using a layout model 3.2.3.1 Article definition

As we said before we define on the image some area of interest representing the following entities: title, text, horizontal separator, and vertical separator. The definition of an article follows some precise layout rules, this is why we consider that an article begins with a "title" entity followed by at least one "text" entity, and ends by a "horizontal separator" entity or another "title" entity. This basic layout model also has to take into consideration the particular case of the articles, which extend on several pages. We consider that a "text" entity placed in the first or in the last position of a list of articles is linked to an article of the previous or the next page of the considered newspaper issue.

Definition of the grid of separators

The horizontal and vertical separators of the newspaper pages constitute robust information to identify the structure of the pages and extract the articles, but these separators are sometimes broken due to the degradations of the document. The vertical separators delimit the columns while the horizontal ones separate either the articles belonging to a column or the different sections of the page. The title areas are also important for the analysis of the logical structure of the page because they allow locating the beginning of an article. Thus the document being analysed can be modelled as a tree of blocks, each one of the blocks representing the different sections of this document. The root of this tree is constituted of one block representing the whole page, as the next levels are constituted by the blocks delimited by the vertical and horizontal separators, and so on. We call hierarchical position, the position of a block or of a separator in the tree representing the structure of the document. The set of all the separators of a given page constitute a logical grid describing the logical structure of the document (figure 1d). We exploit this information to define a list of articles logically arranged and ordered according to the reading order determined both by their position in the document and their hierarchical position in the tree describing the logical structure. Finally one or several boxes of the logical grid compose each one of the extracted articles.

Generation of the grid and text blocks extraction

The first step of our segmentation method consists in prolonging all the area of interest labelled as "separator" or "title" in order to generate a grid of separators representing all the articles of the document. For that we apply the following algorithm:

• Create the vertical and horizontal separator mask Thus we obtain a full grid covering the entire image and then we can use it to extract the articles. For that we generate the list of blocks which correspond to the boxes of our grid and we compare the coordinates of these blocks to the coordinates of the text lines extracted by the procedure explained in the subsection 3.2.2. We extract also the "title" entities and we add to the blocks the text lines which are fully included. The blocks containing no text line are rejected from the list. Finally we obtain a list of boxes positioned on the separator grid, and we only have to use this list of boxes to obtain a list of articles ordered according to the reading order of the document defined by the editorial model. The figure 6 shows an example of reading order interpretation.

Article extraction and reading order determination

The boxes of the previously described grid may contain a full article or part of article. By part of article we mean a textual zone which is broken into several parts and covers several section or pages. To be able to regroup these parts of a same article, it is necessary to identify the reading order in the section including them.

As explained in the subsection 3.2.3.2, the separators divide the page in sections, the sections into subsections and so on up to the block level which corresponds to the leaves of the logical tree model. In the subsection 3.2.3.3 we explained how the boxes of the grid are determined, and we now explain how we determine the sections.

For each section 𝑠, we seek the nearest horizontal separator strictly longer than the considered section and situated just above it. This horizontal separator delimits two sections. Among them the one containing 𝑠 is called the parent section. We repeat this process until having considered the entire tree model from the leaves to the root.

In each intermediate node of the tree, we order the contained children sections. We consider that a section precedes another if its top-left coordinate is strictly on the left or higher in the document image. For the children sections corresponding to the leaves of the tree model, this order relation implies the reading order of these sections. If a longer separator delimits a box which contains no title, it means that this box is the second part of a fragmented article. In this case this part of article is grouped with the box just before it.

Finally at this end of this stage we obtain the list of articles ordered by sections.

Results

This method was tested on a dataset containing 42 document images issued from a French regional newspaper called "Journal de Rouen". The results are determined visually because we do not have the ground-truth data to check them automatically. We determined the detection rate and the over-segmentation rate. These results are given in Table 1. The analysis of the errors produced by our method allow us to see that a great number of them are due to the labelling errors at the output of segmentation stage performed by the CRF model. For example on our test dataset we have 14 text lines labelled by error as "title" causing the creation of a new article when the editorial rules described in subsection 3.2.3.1 are applied, and then we obtain 28 articles instead of the 14 we should find. Theses errors cause in general an over-segmentation.

Full processing system

The method we present in this paper is integrated in a full system able to process a large amount of old newspaper document images. This system first applies on the images binarization and skew correction processing before applying the article extraction method described previously. Then the extracted text lines are used to feed on OCR engine to recognize the textual content. Our system provides as output XML files in METS/ALTO format. These files contain both the logical structure describing the reading order of the articles and the physical layout constituted by the detected text lines and the associated OCR results. They can be used to index the documents to improve the online access to the data they contain in digital archive applications. For that we propose a web newspaper browsing application, which exploits the data produced by the system presented in this paper. This front-end system, which will be presented in a further paper, provides a web high definition visualisation of images, textual indexing and retrieval facilities, searching and reading at the article level. Articles transcriptions can be collaboratively corrected, which as a consequence allows for better indexing. We are currently testing the system on the archives of the Journal de Rouen, one of France eldest local newspaper. These 250 years of publication amount to 300 000 pages of very variable image quality and layout complexity. Test year 1808 can be consulted at plair.univ-rouen.fr.

Conclusion and future work

We presented in this paper a logical segmentation method based on the analysis of low-level labeling results produced by a CRF model, using a set of grouping rules defined by a generic layout model. The proposed method is able to segment the textual content of old newspapers with complex Manhattan structure (multi columns), using a little set of simple rules. We obtain with this method an article segmentation rate of 85.84% on a test dataset containing 42 images of "Journal de Rouen", one of the oldest French regional newspapers.

These first results are promising, and allow us to identify the main improvement issues. In a future work we will improve further both the CRF model and the layout rules in order to be able to take into account some important other entities of the document structure, such as figures, pictures, captions and tables.

•

  Connect the closed vertical separator • Prolong the vertical separators as long as they do not cross a horizontal separator or a title • Connect the closed horizontal separator • Prolong the horizontal separators and the titles as long as they do not cross a vertical separator

[ 5 ]Figure 1 .

 51 Figure 1. (a) original image (b) pixel level logical labeling result (c) labelling smoothing (d) grid of separators (e) result of the segmentation into articles (f) example of reading order

Table 1 . Results of the logical segmentation into articles

 1

	#articles	#detected	#correct	%correct	%over-seg
	226	245	194	85.84	8.41

ACKNOWLEDGMENTS

The PlaiR project (Regional Indexing Platform, in French "Plateforme d'Indexation Regionale") is funded by the "Haute-Normandie" regional council and the European institutions by the FEDER program. This project is supported by the CHU and the University of Rouen.