Siwar Jendoubi
email: jendoubi.siouar@laposte.net

Boutheina Ben
email: boutheina.yaghlane@ihec.rnu.tn

Arnaud Martin
email: arnaud.martin@univ-rennes1.fr

Belief Hidden Markov Model for Speech Recognition

Keywords: Speech recognition, HMM, Belief functions, Belief HMM

Speech Recognition searches to predict the spoken words automatically. These systems are known to be very expensive because of using several pre-recorded hours of speech. Hence, building a model that minimizes the cost of the recognizer will be very interesting. In this paper, we present a new approach for recognizing speech based on belief HMMs instead of probabilistic HMMs. Experiments shows that our belief recognizer is insensitive to the lack of the data and it can be trained using only one exemplary of each acoustic unit and it gives a good recognition rates. Consequently, using the belief HMM recognizer can greatly minimize the cost of these systems.

I. INTRODUCTION

The automatic speech recognition is a domain of science that attracts the attention of the public. Indeed, who never dreamed of talking with a machine or at least control an apparatus or a computer by voice. The speech processing includes two major disciplines which are the speech recognition and the speech synthesis. The automatic speech recognition allows the machine to understand and process oral information provided by a human. It uses matching techniques to compare a sound wave to a set of samples, compounds generally of words or sub-words. On the other hand, the automatic speech synthesis allows the machine to reproduce the speech sounds of a given text. Nowadays, most speech recognition systems are based on the modelling of speech units known as acoustic unit. Indeed, speech is composed of a sequence of elementary sounds. These sounds put together make up words. Then, from these units we seeks to derive a model (one model per unit), which will be used to recognize continuous speech signal. Hidden Markov Models (HMM) are very often used to recognize these units. HMM based recognizer is a widely used technique that allows as to recognize about 80% of a given speech signal, but this recognition rate still not yet satisfying. Also, this method needs many hours of speech for training which makes the automatic speech recognition task very expensive.

Recently, [START_REF] Ramasso | Forward-backward-viterbi procedures in thetransferable belief model for state sequence analysis using belief functions[END_REF], [START_REF] Ramasso | Contribution of belief functions to HMM with an application to fault diagnosis[END_REF] extend the Hidden Markov Model to the theory of belief functions. The belief HMM will avoid disadvantages of probabilistic HMM which are, generally, due to the use of probability theory. Belief functions are used in several domains of research where incertitude and imprecision dominate. They provide many tools for managing and processing the existent pieces of evidence in order to extract knowledge and make better decision. They allow experts to have a more clear vision about their problems, which is helpful for finding better solutions. What's more, belief functions theories present a more flexible ways to model uncertainty and imprecise data than probability functions. Finally, it offers many tools with a higher ability to combine a great number of pieces of evidence.

Belief HMM gives a better classification rate than the ordinary HMM when they are applied in a classification problem. Consequently, we propose to use the belief HMM in the speech recognition process. Finally, we note that this is the first time where belief functions are used in speech processing.

In the next section we talk about the probabilistic hidden Markov model and we define its three famous problems. In Section three we present the probabilistic HMM recognizer, the acoustic model and the recognition process. The transferable belief model is introduced in section four. In section five we will talk about the belief HMM. In section six, we present our belief HMM recognizer, the belief acoustic model and the belief recognition process. Finally, experiments are presented in section seven.

II. PROBABILISTIC HMM

A Hidden Markov Model is a combination of two stochastic processes; the first one is a Markov chain that is characterized by a finite set1 Ω t of non observable N states (hidden) and the transition probabilities, a ij = P s t+1 j | s t i , 1 ≤ i, j ≤ N , between them. The second stochastic process produces the sequence of T observations which depends on the probability density function of the observation model defined as [START_REF] Rabiner | A tutorial on hidden markov models and selected applications in speech recognition[END_REF], in this paper we use a mixture of Gaussian densities. The initial state distribution is defined as π i = P s 1 i , 1 ≤ i ≤ N . Hence, an HMM λ (A, B, Π) is characterized by the transition matrix A = {a ij }, the observation model B = {b j (O t )} and the initial state distribution Π = {π i }.

b j (O t ) = P O t | s t j , 1 ≤ j ≤ N, 1 ≤ t ≤ T [
There exist three basic problems of HMMs that must be solved in order to be able to use these models in real world applications. The first problem is named the evaluation problem, it searches to compute the probability P (O/λ) that the observation sequence O was generated by the model λ. This probability can be obtained using the forward propagation [START_REF] Rabiner | A tutorial on hidden markov models and selected applications in speech recognition[END_REF]. Recursively, it estimates the forward variable:

α t (i) = P (O 1 O 2 . . .O t , q t = s i | λ) (1)
α t (i) = N i=1 α t-1 (i) a ij b j (O t ) (2)
for all states and at all time instant. Then, P (O/λ) = N i=1 α T (i) is obtained by summing the terminal forward variables. Also, the backward propagation can be used to resolve this problem. Unlike forward, the backward propagation goes backward. At each instant, it calculates the backward variable:

β t (i) = P (O t+1 O t+1 . . .O T | q t = s i , λ) (3)
β t (i) = N j=1 a ij b j (O t+1 ) β t+1 (i) (4) finally, P (O | λ) = N i=1 α t (i)β t (i)
is obtained by combining the forward and backward variable. The second problem is named the decoding problem. It searches to predict the state sequence S that generated O. The Viterbi [START_REF] Rabiner | A tutorial on hidden markov models and selected applications in speech recognition[END_REF] algorithm solves this problem. It starts from the first instant, t = 1, for each moment t, it calculates δ t (i) for every state i, then it keeps the state which have the maximum δ t = max q1,q2,...,qt-1 P (q 1 , q 2 , . . . q t-1 , q

t = i, O 1 O 2 . . . O t-1 | λ) = max 1≤i≤N (δ t-1 (i) a ij ) b j (O t ).
When, the algorithm reaches the last instance t = T , it keeps the state which maximize δ T . Finally, Viterbi algorithm back-track the sequence of states as the pointer in each moment t indicates. The last problem is the learning problem, it seeks to adjust the model parameters in order to maximize P (O | λ). Baum-Welch [START_REF] Rabiner | A tutorial on hidden markov models and selected applications in speech recognition[END_REF] method is widely used. This algorithm uses the forward and backward variables to re-estimate the model parameters.

III. PREBABILISTIC HMM BASED RECOGNIZER

A. Acoustic model

The acoustic model attempts to mimic the human auditory system, it is the model used by the HMM-based speech recognizer in order to transform the speech signal into a sequence of acoustic units, this last will be transformed into phoneme sequence and finally the desired text is generated by converting the phoneme sequence into text. Acoustic models are used by speech segmentation and speech recognition systems.

The acoustic model is composed of a set of HMMs [START_REF] Rabiner | A tutorial on hidden markov models and selected applications in speech recognition[END_REF], each HMM corresponds to an acoustic unit. To have a good acoustic model some choices have to be done:

a) The acoustic unit: the choice of the acoustic unit is very important, in fact, the number of them will influence the complexity of the model (more large the number, more complex the model). If we choose a small unit like the phone we will have an HMM for every possible phone in the language, the problem with this choice is that the phone do not model its context. Such a model is called context independent model. These models are generally used for speech segmentation systems. Other units that take the context into account can be used as acoustic unit as the diphone which model the transition between two phones, the triphone which model the transition between three phones, subwords, words. These models are called context dependent models. According to [START_REF] Rabiner | Fundamentals of speech recognition[END_REF], when the context is greater, the recognition performance improve.

b) The model: for each acoustic unit we associate an HMM, then types of HMM model and the probability density function of the observation must be chosen. Generally, leftright models are used for speech recognition and speech synthesis systems [START_REF] Rabiner | A tutorial on hidden markov models and selected applications in speech recognition[END_REF]. In fact, Speech signal has the property that it changes over time, then the choice of the left-right model is justified by the fact that there is no back transitions and all transitions goes forward. The number of states is fixed in advance or chosen experimentally. [START_REF] Carvalho | Concatenative speech synthesis for european portuguese[END_REF], [START_REF] Cox | Techniques for accurate automatic annotation of speech waveforms[END_REF] fixed the number of state to three. This choice is justified by the fact that most phoneme acoustic realization is characterized by three sub-segments, hence we have a state for each sub-segment. [START_REF] Brugnara | Automatic segmentation and labeling of speech based on hiddenmarkov models[END_REF], [START_REF] Toledano | Automatic phonetic segmentation[END_REF] used an HMM of six states. Finally, we choose the probability density function of the observation. They are represented by a mixture of Gaussian pdf, the number of mixtures is generally chosen experimentally.

The next step, consists on training parameters of each HMM using a speech corpus that contains many exemplary of each acoustic unit. Speech segments are transformed into sequence of acoustic vectors by the mean of a feature extraction method like MFCC, these acoustic vectors are our sequence of observations.

Then, HMMs are concatenated to each other and we obtain the model that will be used to recognize the new speech signal. The recognizer contains three levels; the first one is the syntactic level. It represents all possible word sequences that can be recognized by our model. The second level is the lexical level. It represents the phonetic transcription (the phoneme sequence) of each word. Finally, the third level is the acoustic level. It models the realization of each acoustic unit (in this case the phone).

B. Speech recognition process

The model described above is used for the speech recognition process. Let S be our speech signal to be recognized. Recognizing S consists on finding the most likely path in the syntactic network. The first step, is to transform S into a sequence of acoustic vectors using the same feature extraction method used for training, then we obtain our sequence of observation O. The most likely path is the path that maximizes the probability of observing O such the model P (O|λ). This probability can be done either by using the forward algorithm, or the Viterbi algorithm.

IV. TRANSFERABLE BELIEF MODEL

The Transferable Belief Model (TBM) [START_REF] Smets | The transferable belief model[END_REF], [START_REF] Smets | Belief functions and the transferable belief model[END_REF] is a well used variant of belief functions theories. It is a more general system than the Bayesian model.

Let Ω t = {ω 1 , ω 2 , ..., ω n } be our frame of discernment, The agent belief on Ω t is represented by the basic belief assignment (BBA) m Ωt defined from 2 Ω to [0, 1]. m Ωt (A) is the mass value assigned to the proposition A ⊆ Ω t and it must respect: A⊆Ωt m Ωt (A) = 1. Also, we can define conditional BBA. Then we can have m Ωt S t-1 (A) which is a BBA defined conditionally to S t-1 ⊆ Ω t-1 . If we have m Ωt (∅) > 0, our BBA can be normalized by dividing the other masses by 1m Ωt (∅) then the conflict mass id redistributed and m Ωt (∅) = 0.

Basic belief assignment can be converted into other functions. They represent the same information under other forms. What's more, they are in one to one correspondence and they are defined from 2 Ω to [0, 1]. We will use belief bel, plausibility pl and commonality q functions: bel

Ω (A) = ∅ =B⊆A m Ω (B) , ∀A ⊆ ∅, A = ∅ (5) m Ω (A) = B⊆A (-1) |A|-|B| bel Ω (B) , ∀A ⊆ Ω (6)
pl

Ω (A) = B∩A=∅ m Ω (B) , ∀A ⊆ Ω (7) m Ω (A) = B⊆A (-1) |A|-|B|-1 pl Ω B , ∀A ⊆ Ω (8) q Ω (A) = B⊇A m Ω (B) , ∀A ⊆ Ω (9)
m

Ω (A) = A⊆B (-1) |B|-|A| q Ω (B) , ∀A ⊆ Ω (10)
Consider two distinct BBA m Ω 1 and m Ω 2 defined on Ω, we can obtain m Ω 1∩2 through the TBM conjunctive rule (also called conjunctive rule of combination CRC) [START_REF] Smets | Beliefs functions: The disjunctive rule of combination and the generalized bayesian theorem[END_REF] as:

m Ω 1∩2 (A) = B∩C=A m Ω 1 (B) m Ω 2 (C) , ∀A ⊆ Ω (11)
Equivalently, we can calculate the CRC via a more simple expression defined with the commonality function:

q Ω 1∩2 (A) = q Ω 1 (A) q Ω 2 (A) , ∀A ⊆ Ω (12)
V. BELIEF HMM Belief HMM is an extension of the probabilistic HMM to belief functions [START_REF] Ramasso | Forward-backward-viterbi procedures in thetransferable belief model for state sequence analysis using belief functions[END_REF], [START_REF] Ramasso | Contribution of belief functions to HMM with an application to fault diagnosis[END_REF], [START_REF] Serir | Time-sliced temporal evidential networks: the case of evidential hmm with application to dynamical system analysis[END_REF]. Like probabilistic HMM, the belief HMM is a combination of two stochastic processes. Hence, a belief HMM is characterized by:

• The credal transition matrix A = m Ωt a S t-1 i S t
q Ωt+1 α S t+1 j =   S t i ⊆Ωt m Ωt α S t i .q Ωt+1 a [S t i ] S t+1 j   ∩q Ωt+1 b [O t ] S t j + 1 ( 13
)
This last is calculated recursively from t = 1 to T . [START_REF] Ramasso | Contribution of belief functions to HMM with an application to fault diagnosis[END_REF] exploits the conflict of the forward BBA (obtained by using formula 10) to define an evaluation metric that can be used for classification to choose the model that best fits the observation sequence or it can also be used to evaluate the model. Then, given a model λ and an observation sequence of length T , the conflict metric is defined by:

L c (λ) = 1 T T t=1 log 1 -m Ωt+1 α [λ] (∅) (14)
λ * = arg max λ L c (λ) (15)
A credal backward algorithm is also defined, recursively, it calculates the backward commonality from T to t = 1. More details can be found in [START_REF] Ramasso | Forward-backward-viterbi procedures in thetransferable belief model for state sequence analysis using belief functions[END_REF], [START_REF] Ramasso | Contribution of belief functions to HMM with an application to fault diagnosis[END_REF]. For the decoding problem, many solutions are proposed to extend the Viterbi algorithm to the TBM [START_REF] Ramasso | Forward-backward-viterbi procedures in thetransferable belief model for state sequence analysis using belief functions[END_REF], [START_REF] Ramasso | Contribution of belief functions to HMM with an application to fault diagnosis[END_REF], [START_REF] Serir | Time-sliced temporal evidential networks: the case of evidential hmm with application to dynamical system analysis[END_REF]. All of them search to maximize the state sequence plausibility. According to the definition given in [START_REF] Serir | Time-sliced temporal evidential networks: the case of evidential hmm with application to dynamical system analysis[END_REF], the plausibility of a sequence of singleton states S = s 1 , s 2 , . . . , s T , s t ∈ Ω t is given by:

pl δ (S) = pl π s 1 . T t=2 pl Ωt a s t-1 s t . T t=1 pl b s t (16)
Hence, we can choose the best state sequence by maximizing this plausibility. For the learning problem, [START_REF] Ramasso | Contribution of belief functions to HMM with an application to fault diagnosis[END_REF], [START_REF] Serir | Time-sliced temporal evidential networks: the case of evidential hmm with application to dynamical system analysis[END_REF] have proposed some solutions to estimate model parameters, we will talk about the method used in this paper. The first step consists on estimating the mixture of Gaussian models (GMM) parameters using Expectation-Maximization (EM) algorithm. For each state we estimate one GMM. These models are used to calculate m Ωt b [O t ] S t j . [START_REF] Ramasso | Contribution of belief functions to HMM with an application to fault diagnosis[END_REF] proposes to estimate the credal transition matrix independently from the transitions themselves. He uses the observation BBAs as:

m Ωt×Ωt+1 a ∝ 1 T -1 (17) * T t=1 m Ωt b [O t ] ↑Ωt×Ωt+1 ∩ m Ωt+1 b [O t+1 ] ↑Ωt×Ωt+1 where m Ωt b [O t ] ↑Ωt×Ωt+1 and m Ωt+1 b [O t+1 ]
↑Ωt×Ωt+1 are computed using the vacuous extension operator [START_REF] Smets | Beliefs functions: The disjunctive rule of combination and the generalized bayesian theorem[END_REF] of the BBA m Ωt b [O t ] S t j on the cartesian product space as:

m Ωt↑Ωt×Ωt+1 b (A) = m Ωt b (B) if A = B × Ω t+1 0 otherwise (18)
This estimation formula is used by [START_REF] Serir | Time-sliced temporal evidential networks: the case of evidential hmm with application to dynamical system analysis[END_REF] as an initialization for ITS (Iterative Transition Specialization) algorithm. ITS is an iterative algorithm that uses the credal forward algorithm to improve the estimation results of the credal transition matrix. It stops when the conflict metric (formula 14) converged.

VI. BELIEF HMM BASED RECOGNIZER

Our goal is to create a speech recognizer using the belief HMM instead of the probabilistic HMM. HMM recognizer uses an acoustic model to recognize the content of the speech signal. Then, we seek to mimic this model in order to create a belief HMM based one. We should note that existent parameter estimation methods presented for the belief HMM cannot be used to estimate model parameters using multiple observation sequences. This fact should be taken into account when we design our belief acoustic model.

A. Belief acoustic model

In the probabilistic case, we use an HMM for each acoustic unit, its parameters are trained using multiple speech realization of the unit [START_REF] Rabiner | Fundamentals of speech recognition[END_REF], [START_REF] Brugnara | Automatic segmentation and labeling of speech based on hiddenmarkov models[END_REF], [START_REF] Carvalho | Concatenative speech synthesis for european portuguese[END_REF], [START_REF] Toledano | Automatic phonetic segmentation[END_REF], [START_REF] Cox | Techniques for accurate automatic annotation of speech waveforms[END_REF]. In the credal case, a similar model cannot be used. Hence, we present an alternate method that takes this fact into account.

Let K be the number of the speech realization of a given acoustic unit. These speech realization are transformed into MFCC feature vectors. Hence, we obtain K observation sequences. Our training set will be:

O = O 1 , O 2 , . . . , O K where O k = O k 1 , O k 2 , . . . , O k
T k is the k th observation sequence of length T k . These observations are supposed to be independent to each other. So instead of training one model for all observation set O, we propose to create a belief model for each observation sequence O k . These K models will be used to represent the given acoustic unit in the recognition process.

Like the acoustic model based on the probabilistic HMM, we have to make some choices in order to have a good belief acoustic model. In the first place, we choose the acoustic unit. The same choices of the probabilistic case can be adopted for the belief case. In the second place, we choose the model. We should note that we cannot choose the topology of the belief HMM, this is due to the estimation process of the credal transition matrix. In other words, the resultant credal observation model is used to estimate the credal transition matrix which does not give as the hand to choose the topology of our resultant model. Consequently, choosing the model in the credal case consists on choosing the number of states and the number of Gaussian mixtures. In our case we fix the number of states to three and we choose the number of Gaussian mixtures experimentally.

B. Speech recognition process

The belief acoustic model is used in the speech recognition process. Now, we explain how the resultant model will be used for recognizing speech signal.

Let S be our speech signal to be recognized. Recognizing S consists on finding the most likely set of models. The first step, is to transform S into a sequence of acoustic vectors using the same feature extraction method used for training, then we obtain our sequence of observation O. This last is used as input for all models. The credal forward algorithm is then applied, each model gives us an output which is the value of the conflict metric. An acoustic unit is presented by a set Then we calculate the arithmetic mean of the resultant values. Finally, we choose the set of models that optimizes the average of the conflict metric instead of optimizing the conflict metric, as proposed by [START_REF] Ramasso | Contribution of belief functions to HMM with an application to fault diagnosis[END_REF], using formula 15.

VII. EXPERIMENTS

In this section we present experiments in order to validate our approach. We compare our belief HMM recognizer to a similar one implemented using the probabilistic HMM.

We use MFCC (Mel Frequency Cepstral Coefficient) as feature vectors. Also, we use a three state HMM and two Gaussian mixtures. Finally, to evaluate our models we calculate the percent of correctly recognized acoustic units (number of correctly recognized acoustic unit / total number of acoustic units). We use a speech corpus that contains speech realization of seven different acoustic units and we have fifteen exemplary of each one. Results are shown in figure 1.

The lack of data for training the probabilistic HMM leads to a very poor learning and the resultant acoustic model cannot be efficient. Then using a training set that contains only one exemplary of each acoustic unit leads to have a bad probabilistic recognizer. In this case our belief HMM based recognizer gives a recognition rate equal to 85.71% against 13.79% for the probabilistic HMM which is trained using HTK [START_REF] Young | The htk book for htk version 3.4[END_REF]. This results shows that the belief HMM recognizer is insensitive to the lack of data and we can obtain a good belief acoustic model using only one observation for each unit. In fact, the belief HMM models knowledge by taking into account doubt, imprecision and conflict which leads to a discriminative model in the case of the lack of data.

HTK is a toolkit for HMMs and it is optimized for the HMM speech recognition process. It is known to be powerful under the condition of having many exemplary of each acoustic unit. Hence, it needs to use several hours of speech for training. Having a good speech corpus is very expensive which influence the cost of the recognition system. Then, the speech recognition systems are very expensive. Consequently, using the belief HMM recognizer can greatly minimize the cost of these systems.

VIII. CONCLUSION

In this paper, we proposed the Belief HMM recognizer. We showed that incorporating belief functions theory in the speech recognition process is very beneficial, in fact, it reduces considerably the cost of the speech recognition system. Future works will be focuced on the case of the noisy speech signal. Indeed, existent speech recognizer still not yet good if we have a noisy signal to be decoded.

,•

  functions defined conditionally to all possible subsets of states S t-1 i The observation model B = m Ωt b [O t ] S t j a set of BBA functions defined conditionally to the set of possible observation O t , • The initial state distribution Π = m Ω1 π S Ω1 i . The three basic problem of HMM and their solutions are extended to belief functions. As we know the forward algorithm resolves the evaluation problem in the probabilistic case. [7] introduced the credal forward algorithm in order to resolve this problem in the evidential case. It needs as inputs m Ωt b [O t ] S t j to calculate the forward commonality:

Figure 1 .

 1 Figure 1. Influence of the number of observations on the recognition rate

t notes the current instant, it is put in exponent of states for simplicity.


Ana B Graciano Fouquier

Stanley Durrleman
email: stanley.durrleman@inria.fr

Jérôme Yelnik

Sara Fernández-Vidal
email: sara.fernandezvidal@upmc.fr

Eric Bardinet
email: eric.bardinet@upmc.fr

Iconic-Geometric Nonlinear Registration of a Basal Ganglia Atlas for Deep Brain Stimulation Planning

Keywords: nonlinear registration, diffeomorphism, basal ganglia, subthalamic nucleus, Parkinson's disease, deep brain stimulation

This paper evaluates a nonlinear registration method for warping a 3D histological atlas of the basal ganglia into patient data for deep brain stimulation (DBS) planning. The power of the method is the possibility to combine iconic registration with geometric constraints under a unified diffeomorphic framework. This combination aims to ensure robust and accurate atlas-to-patient warping and anatomy-preserving deformations of stimulation target nuclei. A comparison of the method with a state-of-the-art diffeomorphic registration algorithm reveals how each approach deforms low-contrasted image regions where DBS target nuclei often lie. The technique is applied to T1-weighted magnetic resonance images from a cohort of Parkinsonian subjects, including subjects with standard-size and large ventricles. Results illustrate the effects of iconic or geometric registration alone, as well as how both constraints can be integrated in order to contribute for registration precision enhancement.

Introduction

In deep brain stimulation surgical planning, targeting of the basal ganglia is an important step, since it allows to estimate the location of target nuclei in the patient's brain. These estimates are used to plan the possible trajectories for electrode implantation during surgery. Precise positioning of electrodes is a key factor for the success of DBS, since stimulation of areas surrounding the target nuclei instead of the nuclei themselves, or stimulation of distinct territories within the same target, such as the motor or limbic parts of the subthalamic nucleus (STN), may account for drastic negative side-effects [START_REF] Groiss | Deep brain stimulation in parkinson's disease[END_REF][START_REF] Mallet | Stimulation of subterritories of the subthalamic nucleus reveals its role in the integration of the emotional and motor aspects of behavior[END_REF][START_REF] Welter | Optimal target localization for subthalamic stimulation in patients with parkinson disease[END_REF].

Automatic atlas registration methods are among the solutions [START_REF] Bardinet | A three-dimensional histological atlas of the human basal ganglia. II. Atlas deformation strategy and evaluation in deep brain stimulation for parkinson disease[END_REF][START_REF] Chakravarty | Comparison of piece-wise linear, linear, and nonlinear atlas-to-patient warping techniques: Analysis of the labeling of subcortical nuclei for functional neurosurgical applications[END_REF][START_REF] Guo | Comparison of different targeting methods for subthalamic nucleus deep brain stimulation[END_REF] for anatomical targeting. These methods usually depend on the data to be registered, on a transformation model of the possible deformations (rigid, affine, nonlinear), and on a similarity measure to align atlas and patient data. The suitability of each transformation type and similarity criterion depends on the problem at stake. A registration method suitable for DBS applications should be able to map a basal ganglia atlas to a patient's brain robustly and accurately, while respecting anatomical constraints. For example, although inter-subject variability of subcortical structures is natural, these structures may share common shape patterns that are not expected to change significantly unless a pathology induces such deformations. However, targeting of DBS nuclei in images may be difficult, since certain nuclei (e.g. STN) are hardly or only partially visible in 1.5T T1 or T2-weighted magnetic resonance images (MRI). In these cases, the estimation of target nuclei location must rely on their surrounding visible structures.

This paper evaluates a nonlinear registration algorithm applied to the problem of atlas-to-patient basal ganglia registration of 1.5T T1-weighted MRI from DBS-eligible patients treated in the local neurosurgical department. This new method aims at improving, by means of nonlinear deformations, the accuracy of the current two-step rigid/affine registration, which is not always capable of satisfactorily registering the atlas data to the patient brain, especially in the case of subjects with large ventricles. This deformation model introduces a unified formalism for the use of geometric and iconic constraints. Iconic information is often considered when aligning image contours that are present everywhere in the image domain. Also, labeled structures segmented from images and represented by geometric entities (e.g. 3D surface meshes) may be used as geometric constraints. However, geometric registration is defined only on the contours to be aligned, and does not cover the whole image domain as in the iconic case.

The main advantage of the unified approach is thus the possibility to combine iconic and geometric information, since geometry can be used as a constraint to guide local anatomical deformations, whereas the intensity-based information can account for deformations in other regions. This combination is attained by choosing a suitable deformation defined in the ambient space (the domain embedding images and surfaces to be registered), which is also applicable to every object embedded in such a space. This is possible because the parametrization of deformations is made independent of the data to be registered. Our experiments show how each of these constraints alone influences registration, as well as how they can be put together to improve atlas-to-patient warping. Results also show that the modeled class of diffeomorphisms produces desirable anatomy-preserving deformations of the subthalamic nucleus, unlike other nonlinear state-of-the-art methods.

Iconic-Geometric Diffeomorphic Nonlinear Registration

Consider a total of N obj deformable objects (e.g. images, surfaces). Let S k , k = 1 . . . N obj , be a source object to be registered to a target object T k , and let M k be its corresponding deformed object. Our purpose is to find a compound registration from these sources to their respective targets. Such a registration corresponds to a single diffeomorphic transformation φ c,α of the whole 3D space embedding all these objects, which is obtained thanks to the control point formulation introduced in [START_REF] Durrleman | Morphometry of anatomical shape complexes with dense deformations and sparse parameters[END_REF] for geometric entities (curves, surfaces, etc.) 6 and in [START_REF] Durrleman | Sparse adaptive parameterization of variability in image ensembles[END_REF] for images. The proposed formalism is built on these works and unifies the geometric and iconic diffeomorphic registrations under a single model.

Diffeomorphic deformations of all points in the ambient space are obtained through the integration of a time-varying vector field over the time interval [0, 1], given by v t (x) =

N C i K(x, c i (t))α i (t)
. Each α i is a momentum vector associated to a control point c i out of a total of N C control points. These control points are not defined over the input data, but they are optimized within the ambient space and tend to move towards the most variable parts of the data. The previous equation defines a parametrization of diffeomorphisms that depends on the interpolation of the set of momenta located at the control points. It also describes the velocity of any point in the ambient space x at time t ∈ [0, 1]. K is an interpolation Gaussian kernel that defines a Reproducing Kernel Hilbert Space (RKHS) and is given by K(x, y) = exp (-||x-y|| 2 )/σ 2 g . This shows that the deformation integrates iconic and geometric information contained in a neighborhood of size σ g ∈ ℜ, whereas points farther than σ g from image contours or surfaces almost do not move.

To compute the compound registration of the set of deformable objects, which corresponds to a diffeomorphic transformation of the ambient space, we need to estimate the position of these control points and associated momenta. Given an initial set c 0 of control points and their associated set α 0 of initial momenta, this registration is achieved by minimizing the following objective function:

E(c 0 , α 0 ) = ( N obj k=1 1 2σ k 2 D(φ c,α * M k , T k ) 2 ) + Reg(φ c,α ) , ( 1
)
where D is a similarity measure computed between each transformed source data and their corresponding target, and Reg is a regularity term defined over the diffeomorphic transformation φ c,α . For more details on the diffeomorphism φ c,α , the reader is referred to [START_REF] Durrleman | Morphometry of anatomical shape complexes with dense deformations and sparse parameters[END_REF][START_REF] Durrleman | Sparse adaptive parameterization of variability in image ensembles[END_REF].

The parameter σ k ∈ ℜ is of great importance. It consists in a scalar tradeoff value between fidelity-to-data and the regularity of the sought deformation. It also balances the relative importance of each iconic and geometric constraint among themselves. Besides this, the underlying parameter σ g plays a crucial role in the interpolation of geometric and iconic information present in the ambient space, as discussed previously in this section. It also regulates the scale at which deformations are taken into account. A small kernel will tend to consider local variations, which may be desirable when trying to register refined anatomical details, whereas a larger kernel will promote more homogeneous deformations.

If S k and T k are images, the similarity measure D is based on the quadratic error to the local affine model proposed in [START_REF] Cachier | Iconic feature based nonrigid registration: The PASHA algorithm[END_REF], which is more robust to source and target contrast differences than whole-image measures such as the sum of squared differences. This distance is defined as:

D(φ c,α * M k , T k ) 2 = (σ 2 p (φ c,α * M k ) - Corr(T k , φ c,α * M k ) 2 p σ 2 p (T k ) )dp. (2)
Corr(I, J) is the local correlation between two given images I and J , defined over a symmetric and normalized window function W : ℜ d → ℜ. Let W p be the window translation around a point p and let x be a point in the images domain.

Then Corr(I, J) is written as:

Corr(I, J) p = W p (x)(I(x) -W p (x)I(x)dx)(J(x) -W p (x)J(x)dx)dx.
(3) Besides, σ 2 p (I) is the local variance of a given image I, written as:

σ 2 p (I) = Corr(I, I) p . ( 4
)
If S k and T k represent geometric primitives, D is a point-correspondence-free distance on varifolds, which are the adopted mathematical representations of geometric deformable objects in this formulation. When M k and T k are surfaces represented by computer meshes, the similarity measure is written as:

D(φ c,α * M k , T k ) 2 =< φ c,α * M k , φ c,α * M k > + < T k , T k > -2 < φ c,α * M k , T k > , (5)
where the operator < S, S ′ > represents the inner product of two given surfaces S and S ′ represented by computer meshes and defined as:

< S, S ′ >= s s ′ K W (p s , p s ′ ) (n T s n s ′ ) 2 |n s ||n s ′ | , (6)
where s (resp. s ′ ) is the total number of mesh cells composing the surface, p s and n s (resp. p s ′ and n s ′ ) represent the centers and normals of the faces in S (resp. S ′ ), and |n s | (resp. |n s ′ |) is the area of each mesh cell. Finally, K W is a Gaussian function with a fixed standard deviation σ W .

Atlas-to-Patient Registration

In the local neurosurgical department, targeting of basal ganglia is currently achieved through atlas-to-patient registration. DBS-eligible patient data consists of pre-operative T1-weighted MRI acquired with a GE R 1.5T scanner. The adopted atlas was described in [START_REF] Bardinet | A three-dimensional histological atlas of the human basal ganglia. II. Atlas deformation strategy and evaluation in deep brain stimulation for parkinson disease[END_REF][START_REF] Yelnik | A three-dimensional, histological and deformable atlas of the human basal ganglia. I. Atlas construction based on immunohistochemical and MRI data[END_REF] and consists in a detailed 3D histological model of the human basal ganglia, obtained through the co-registration of histological and T1-weighted MRI data from a post-mortem specimen, which may be adapted into patient's space. Then, targeting of the basal ganglia follows a pipeline that is similar to the inclusion protocol described in [START_REF] D'albis | Pydbs: an automated image processing workflow for deep brain stimulation surgery[END_REF]: first the AC-PC coordinates are interactively defined over the patient's MRI; then, the scalp, gray/white matter, and sulci are segmented from the T1-weighted MRI; finally, spatial normalization of the patient data in the atlas space is performed. This normalization is achieved through a patient-to-atlas two-step image registration process. The patient's MRI is rigidly registered to the atlas MRI for brain volume alignment. Next, the result and the atlas image are cropped into two regions of interest (ROI) around the basal ganglia, resulting in right and left hemisphere ROIs. Finally, each hemispheric patient ROI is registered to the corresponding atlas ROI, through affine transforms, allowing for a more refined alignment of data around the basal ganglia. Examples of the atlas cropped volume and the registered input cropped volumes are shown in Fig. 1. All registrations are done with the Baladin software [START_REF] Yelnik | A three-dimensional, histological and deformable atlas of the human basal ganglia. I. Atlas construction based on immunohistochemical and MRI data[END_REF], a multiscale block-matching algorithm. Finally, the atlas meshes are deformed into the original patient MRI space by applying the composition of atlas-to-patient affine and rigid matrices to each mesh. This allows for easy assessment 7 of registration quality directly over the patient MRI. Although this pipeline is robust for STN targeting, the Fig. 2. Registration deformations obtained from the Baladin algorithm (brighter colors) and from ANTS with standard parameters (darkers colors), applied to meshes of the caudate nucleus (green), thalamus (red), putamen (pink), and subthalamic nucleus (yellow/orange). These meshes were warped into the image space of a subject D with standard-size ventricles (top) and a subject E with large ventricles (bottom). Although ANTS produces accurate caudate and thalamus registrations, its deformations implied onto the STN do not preserve anatomy.

rigid-affine combination is not always accurate for dealing with patient-to-atlas deformations that are of nonlinear nature. For instance, one common pitfall concerns the caudate nucleus, whose corresponding region tends to go over the actual ventricle region after registration, as seen in Fig. 2. This typical problem leads us to consider the adoption of a nonlinear registration step in the basal ganglia targeting pipeline.

Nonlinear registration methods may cope with broader types of deformations and, thus, produce more precise patient-to-atlas registration, but a common drawback is that they may also lead to spurious deformations due to image noise or to the way the deformation model acts in low-contrast image regions. For instance, the software ANTS [START_REF] Avants | Symmetric diffeomorphic image registration with cross-correlation: Evaluating automated labeling of elderly and neurodegenerative brain[END_REF][START_REF] Klein | Evaluation of 14 nonlinear deformation algorithms applied to human brain MRI registration[END_REF] accurately aligns anatomical structures that present high contrast and are fairly visible in a given image, such as the caudate, the ventricles, and the thalamus. However, structures present in lowcontrast image regions, e.g. the STN, are deformed in an unrealistic manner. This effect is shown in Fig. 2 for the STN, whose left-hemispheric 3D histological mesh was warped into patient space according to the deformation field found by ANTS for atlas-to-patient registration. In the ANTS deformation model, image forces computed in high-contrast regions propagate to low-contrast regions and dominate the deformation of the more homogeneous regions. Thus, the good accuracy in the alignment of highly-contrasted structures is done at the cost of less controlled deformations in low-contrast regions. On the other hand, the registration model proposed in Sect. 2 deals with low-contrasted and weak-gradient regions in a distinct manner. It tends to penalize deformations in such regions, leading to anatomy-preserving deformations of the STN. Next, we discuss the experimental assessment of this method.

Experimental Results

For these experiments, subcortical structures surfaces represented by meshes were obtained with the automatic subcortical segmentation procedure reconall [START_REF] Fischl | Whole brain segmentation: automated labeling of neuroanatomical structures in the human brain[END_REF], from the Freesurfer image analysis suite, which provides reasonable segmentations. Although the 3D histological atlas meshes are available, we also extracted subcortical structures from the atlas MRI using this software, in order to register meshes with the same level of detail. We adopted the left hemispheric lateral ventricle and caudate provided by Freesurfer as geometric constraints for our tests. For atlas-to-patient registration assessment, we warped the 3D histological atlas meshes according to each resulting diffeomorphic deformation, and subsequently transformed them into the original patient MRI space in the same way as explained in Sect. 3. The method was tested on the registered cropped volumes from the five patients depicted in Fig. 1. For illustration purposes, here we only show results for subjects A, D, and E, who present thinner, similar and larger ventricles with respect to the atlas postmortem specimen. Iconic Registration. Consider the atlas left-hemispheric ROI, and the affinelyregistered left-hemispheric ROI obtained for a given patient, as explained in Sect. 3. This first experiment consisted in registering the atlas ROI to the patient's ROI, using σ g = 3mm as the convolution parameter, and σ 1 = 0.71 for the image data-fidelity parameter. The Gaussian kernel is small enough to capture image deformations occurring within small image regions, whereas the data-fidelity term was chosen in a way as to give as much importance to the data as to the allowed regularity of the sought deformation.

Figure 3 depicts registration results for subject A, whose lateral ventricles are smaller than those from the postmortem specimen, subject D, whose ventricles are of standard-size, and subject E, whose lateral ventricles are much larger. In all three cases, there is an improvement in the caudate and the thalamus registrations in comparison with the Baladin results. The chosen parameters Fig. 3. Meshes warped according to our nonlinear registration using only iconic constraints (darker colors) and the Baladin algorithm (brighter colors) for subjects A (top), D (middle), and E (bottom). The color-structure correspondence is the same as that of Fig. 2 and will be consistently adopted throughout the paper. Although registration is enhanced in comparison with Baladin results, caudate accuracy still requires improvements, especially for subject E presenting large ventricles.

are suitable for obtaining a satisfying registration for subjects with standardsize ventricles. However, results are poorer for the subject with large ventricles, especially concerning the caudate-ventricle superposition. This is probably due to the size of σ g , which is small in comparison with the ventricle or caudate differences between the atlas and this patient. In this case, the kernel K applied to each control point does not consider image gradients that are farther than σ g and registration does not capture this large dissimilarity. Increasing the value of σ g and/or adjusting the data-fidelity value could lead to better results.

Geometric Registration. This second experiment consisted in registering the atlas caudate mesh obtained from Freesurfer to the patient's respective Freesurfer mesh, using σ g = 3mm, and σ 1 = 0.71 as the geometric data-fidelity parameter. Here, the sought diffeomorphism only considers geometric constraints. The caudate is the structure of choice, since it is one of the main structures whose registration must be improved. Figure 4 shows the results of the warpings of the atlas meshes according to the deformations found for the same subjects as before. In all three cases, the caudate-ventricle superposition problem is reduced with respect to the Baladin results. Also, atlas mesh alignment is improved for subjects D and E in comparison with the iconic case, even though the parameters are the same in both cases. However, the registration does not affect the whole thalamus, and this structure is only slightly enhanced. This is because geometric deformations decay exponentially as they move away from the surface mesh, according to the value of σ g . Thus, they can only influence nearby regions, as it can be seen in the thalamus frontier close to the caudate in sagittal and coronal views.

Iconic-Geometric Registration. This last experiment consisted in registering simultaneously the atlas left lateral ventricle and caudate meshes obtained from Freesurfer, and its left hemispheric ROI to the patient's respective meshes and ROI. The adopted parameter values were σ g = 5mm and σ 1 = σ 2 = σ 3 = 0.1. In this test, more importance was given to the geometric and iconic constraints with respect to the regularity term. The lateral ventricles and caudate nuclei were used as geometric constraints in the attempt to enhance registration for the subject with large ventricles. Results are illustrated in Fig. 5. Atlas mesh alignment for each basal ganglia structure is more precise in comparison with the iconic case and the results from Baladin. Unlike the purely geometric registration, improvements also occur in other image regions, such as in the thalami or putamen of these subjects since the iconic information also drives the registration.

Discussion

The results discussed in Sect. 3.1 show that our nonlinear diffeomorphic registration method is capable of improving atlas-to-patient registration where the current two-step rigid and affine combination presents drawbacks. The registration of the caudate was improved with respect to the accumbens area, and Fig. 4. Meshes warped according to our nonlinear registration using the caudate nuclei meshes as geometric constraints (darker colors) and the Baladin algorithm (brighter colors) for subjects A (top), D (middle) and E (bottom). Warping of the caudate is more accurate than in the iconic case for subjects D and E, but the underlying deformations do not affect other structures, especially those far from the adopted geometrical constraint. Fig. 5. Meshes warped according to our nonlinear registration using iconic and geometric constraints (darker colors), expressed by the lateral ventricles and caudate nuclei mesh, and the Baladin procedure (brighter colors) for subjects A (top), D (middle), and E (bottom). Caudate registration was enhanced for all subjects, while farther regions (e.g., the thalamus) were also deformed thanks to the iconic information simultaneously considered during the registration process. Fig. 6. Caudate and STN meshes deformed according to: ANTS, iconic information alone, geometric information alone, and combined iconic-geometric information for subjects A-E. The original atlas meshes are shown in the leftmost column as an anatomical reference. Meshes warped according to the deformations produced by our approach are more robust with respect to anatomy than those warped with ANTS.

ventricle-superposition was reduced in all three experiments. Thalamus registration was also enhanced. When merely geometric registration is considered, deformations impact only the regions surrounding the registered structure. To deform other regions in space, a set of geometric constraints covering various regions (e.g. thalamus, caudate, ventricle, putamen) should be registered simultaneously. On the other hand, the exclusive use of geometric constraints may also imply a dependence between registration quality and segmentation accuracy. If the input meshes come from successful segmentations, the geometric registration succeeds. Otherwise, it may fail. This sensitivity to input mesh quality, as well as the global deformation issue, can be both dealt with by the iconic-geometric approach, since it allows the introduction of geometric constraints, while it still considers intensity cues. Thus, this solution benefits from both sources of information to improve atlasto-patient registration as shown by our results. In this type of registration, the challenge is to choose the parameters corresponding to the data-fidelity term for each source of information in order to seize the best iconic-geometric compromise. Concerning parameters, the choice of σ g is also crucial, because of its role in data interpolation and its direct influence in registration results.

In our qualitative comparative study, the experiments show that our nonlinear registration method may be less accurate than ANTS in high-contrast regions, especially when using only iconic constraints, but the underlying diffeomorphic model better controls the impact of deformations in low-contrast regions, where the main DBS targets lie. Since the STN lies in such low-contrasted regions, warpings of the STN produced by our three diffeomorphic approaches (iconic, geometric, and iconic-geometric) respect the ovoid shape of this structure better than ANTS, as Fig. 6 shows8 . On the other hand, ANTS registrations using the suggested default parameters produce less realistic shapes from an anatomical point of view. Even though structures such as the caudate are well-registered through ANTS, the STN is affected drastically by the resulting warpings. Tests with other combinations of ANTS registration parameters should be done to verify if anatomy could be preserved. These fundamental differences are likely due to the distinct diffeomorphic deformation and regularity models adopted in ANTS and in our approach, as highlighted in Fig. 7. This figure presents the deformation fields obtained with ANTS registration for subject E, as well as with the three approaches discussed herein. These images show how each method deforms the original atlas cropped volume and its meshes according to the iconic and/or geometric information used. As a next step, we plan to perform a quantitative evaluation of the shape and location variations of the STN according to the deformations implied by the different registration approaches discussed herein.

Figure 8 depicts the STN meshes of subject E (large ventricles), warped according to ANTS, the iconic, geometric, and iconic-geometric approaches respectively, and superposed onto the T2 MRI corresponding to this subject. Because the STN and other targeted nuclei are not visible in 1.5T T1 MRI, we resorted to 1.5T T2 MRI images of the test subjects for a qualitative assessment of our registrations. These images may be used for visual inspection and estimation of the STN location [START_REF] Bejjani | Bilateral subthalamic stimulation for parkinson's disease by using three-dimensional stereotactic magnetic resonance imaging and electrophysiological guidance[END_REF], since it is partially visible as a hypo-intense signal, and surrounding nuclei, such as the red nucleus or the substantia nigra, are also visible and can be used as a visual guide for the STN location. Note that, despite this visibility, the STN structure cannot be completely defined from T2 MRI alone, since these images are not anatomical, thus requiring other sources of information (such as the T1-MRI atlas-based registration, electrophysiological recordings) to achieve satisfactory targeting. One can verify that the ANTS warping distorts the STN structure and increases it in the anteroposterior and axial axes (sagittal view), which is not desirable. It also moves the STN slightly into the substantia nigra (coronal view). The geometric registration produces a warping that almost does not change the original mesh adapted according to the Baladin registration transformation. This result is explained by the reasons we evoked previously in Sect. 3.1. Finally, the iconic and the iconic-geometric warpings show that the STN moves towards its likely position. Fig. 7. Deformation fields produced by the registration of the atlas to subject E. Each field must be applied to the original atlas T1 MRI cropped volume and its corresponding meshes, shown in each row. For visualization purposes, the atlas STN is shown here in orange. From top to bottom: deformation field obtained using ANTS, iconic information alone, geometric information alone, and combined iconic-geometric information respectively. The low-contrasted image regions around the STN are less impacted by our three approaches than with ANTS. Fig. 8. Atlas STN meshes adapted according to the registration using Baladin (yellow) and warped according to the nonlinear registration algorithms (orange) superposed onto the 1.5T T2-MRI from subject E. From top to bottom: 1.5T T2-MRI slices (from left to right: sagittal, coronal, axial), and warped STN meshes obtained using ANTS, iconic information alone, geometric information alone, and combined iconic-geometric information respectively. Regions covered by ANTS-warped STN meshes overgo the STN regions, whereas our iconic and iconic-geometric approaches move it closer to the real STN position in the MRI.

All in all, we expect these improvements in atlas-to-patient registration precision to contribute for better surgical planning of the DBS electrode implantation trajectories to reach the targeted basal ganglia nuclei. This is particularly important, as the desirable location of electrode implantation becomes more and more refined, as it is the case of the STN and its limbic, sensorimotor and associative functional subterritories [START_REF] Welter | Optimal target localization for subthalamic stimulation in patients with parkinson disease[END_REF]. The higher precision alone cannot ensure the successful final outcome of DBS, since other possible sources of errors and imprecision may influence the pre-operative (e.g.: subcortical segmentation errors) and intra-operative procedures (e.g.: brain shift). Obviously, we believe that improving precision at each step of this complex process is an advisable practice. In this work, we focused on the accuracy improvement of the atlas-based targeting method. Although these preliminary results were obtained for a reduced cohort of patients, the respective data were representative of the broader population treated at the hospital, which encourages us to pursuit further testing and validation.

Fig. 1 .

 1 Fig. 1. Atlas left-hemispheric cropped volume from the post-mortem specimen MRI used in the registration process (top row, first three views to the left) and registered MRI left-hemispheric cropped volumes from five subjects of the local cohort of patients liable to DBS. For the atlas and for each subject, sample axial, sagittal, and coronal slices are shown from left to right.

This diffeomorphic registration of geometric objects is implemented in the software Deformetrica, publicly available at http://www.deformetrica.org

Results visualized with the software 3D Slicer (http://www.slicer.org).

The ShapePopulationViewer (http://www.nitrc.org/projects/shapepopviewer/) extension for 3D Slicer was used for visual comparison of the warped surfaces.

Acknowledgements. This research was partially funded by the program "Investissement d'Avenir ANR-10-AIHU-06" of the French Government. The authors would also like to thank the French Research Agency (ANR) for funding this study through the ACouStiC project (ANR 2010-BLAN-0209).


Cvetana Krstev
email: cvetana@matf.bg.ac.yu

Duško Vitas
email: vitas@matf.bg.ac.yu

Restructuring Lemmas in a Dictionary of Serbian

Traditionally produced lexical resources for Serbo-Croatian are not suitable for automatic processing of contemporary Serbian. More specifically, the processes of structural derivation, although very productive in Serbian, are not presented in either monolingual or bilingual dictionaries in a systematic way. The morphological e-dictionary of Serbian was initially produced on the basis of traditional resources and as such reproduces the same flaws. In order to overcome them two solutions are possible. One is to put in the edictionary all the lemmas produced by structural derivation, no matter whether they are recorded in traditional dictionaries and confirmed in the corpus of contemporary Serbian, and then to assemble them explicitly in a complex lemma by an appropriate lexical graph. This approach, however, implies an overproduction of lemmas and the construction of such a graph for each complex lemma. Another approach is to extrapolate the missing lemmas using morphological grammars that model specific morphological processes and that are applied only to the entries already in the dictionary, which is checked by using the lexical constraints. It is demonstrated that such morphological grammars enable a precise classification of processes of structural derivation in a way similar to the classification of inflective phenomena.

Introduction

Traditionally produced Serbian lexical resources are not suitable for automatic processing of contemporary Serbian. The reasons derive from the lack of a clear theoretical and/or methodological frame used for the lexicographic processing that leads to the imprecision of the grammatical description or unsystematic choice of lemmas.

The only complete explanatory dictionary of Serbo-Croatian [START_REF] Rmsmh | Rečnik srpskohrvatskoga književnog jezika[END_REF] is based on manual and partial excerption from the Serbo-Croatian sources compiled before 1960. The consequences can be seen in the years-long postponement of finalization of the one-volume dictionary of contemporary Serbian that was envisaged as the abridgement of [START_REF] Rmsmh | Rečnik srpskohrvatskoga književnog jezika[END_REF]. Another, less visible consequence of the traditional frame of lexicographic processing is seen in the limited production of bilingual dictionaries.

In the field of the Serbian computational lexicography, which is being developed mostly outside the traditional lexicographic circles, resources have been produced that enable a different organization of the dictionary entry in Serbian. In this paper a part of this organization will be presented.

LEMMA

The outline of the problem

We will illustrate the problems that traditional processing poses to the development of lexical resources with one characteristic example, the entry profesor 'professor' (see Table 1). It belongs to the class of masculine gender nouns with unmarked inflection, and as such represents the prototype of inflection for this class. Thus, in [START_REF] Rmsmh | Rečnik srpskohrvatskoga književnog jezika[END_REF] only the information on gender is given in the part for the grammatical definitions, while all other information is being omitted, as for instance the information on animateness, that determines its accusative form.

Three entries that follow in (RMSMH, 1967) (rows 2-4 in Table 1) represent examples of structural derivation in Serbian. By structural derivation we mean the derivational processes that yield a predictable meaning of the word derived from the source word.

Structural derivation is a very productive phenomenon in Serbian that generates a number of lemmas, either by processes illustrated in Tables 1 and3 or some other. Lemmas profesorica and profesorka are combined into one entry. They represent the phenomenon of gender motion that is traditionally seen as the process Nmasc → Nfem, where Nfem often has the meaning 'woman that is Nmasc'. In the part for grammatical definitions only their gender is given, which misleads to the conclusion that in this case the nouns also have an unmarked inflection. This, however, is not the case (Table 2 (sveučilišni) profesor '(university) professor' professor

US u značenju nastavnik 'US, meaning teacher'

Table 6: Lemma profesor and its derivatives in [START_REF] Filipović | English-Croatian or Serbian Dictionary, Školska knjiga[END_REF] Similar is true for the lemma profesorčić, diminutive of profesor (row 4, Table 1). This lemma is produced by structural derivation from the masculine gender noun. It should be noted, however, that the attribute 'pejorative' is not necessarily linked to diminutive and is context dependent. Lemma profesorski,-a,-o (row 3, Table 1) is the relational adjective: the fact is expressed by addition of endingsa,-o. This type of adjectives is derived regularly from the source noun, and in [START_REF] Rmsmh | Rečnik srpskohrvatskoga književnog jezika[END_REF] they have prototypical definitions. The last column in Tables 1 and3 give the frequencies of these dictionary entries established on the corpus of contemporary Serbian SrpCor [START_REF] Vitas | An Overview of Resources and Basic Tools for Processing of Serbian Written Texts[END_REF].

Lemmas from Table 3 are not recorded in (RMSMH, 1967) although they are derived by similar derivational processes. The definitions in Table 3 are prototypical and are used for other lemmas in the same dictionary. For instance, for glumac 'actor' some other derivational lemmas are listed, such as glumičin 'belonging to actress' and glumčina 'augmentative of actor', while some are missing, though recorded in SrpCor, such as glumičica 'diminutive of actress'. These lemmas form the part of a family of words with the noun profesor in a core, while relations between the lemmas in the family have a predictable meaning. For instance, notice in Table 1 that the possessive adjective profesorov is used in the definition of the meaning 2.2, profesorova žena, although the adjective itself is not an entry in (RMSMH,1967).

The consequences of the unsystematic processing of the structural derivation are reflected in the bilingual dictionaries as well. For instance, in the Slovenian/Serbo-Croatian dictionary [START_REF] Jurančić | Slovensko srpskohrvatski rečnik, Državna založba[END_REF] lemmas listed in Table 4 are recorded.

Figure 1: Graph for super-lemma profesor Lemmas on the Serbo-Croatian side of this dictionary correspond to lemmas in (RMSMH, 1967) listed as 1, 2, and 3 in Table 1. The same entries are given also in the Croatian/English dictionary (Bujas, 2001), cited in a simplified way in Table 5. Superscripts in the English column indicate the gender motion (30), and reference from the variant prevailing in Serbian (16). Finally, only one entry is found in the English/Croatian or Serbian dictionary [START_REF] Filipović | English-Croatian or Serbian Dictionary, Školska knjiga[END_REF]) (Table 6).

It should be noted that indications of the inflective properties of the Serbo/Croatian equivalents in bilingual dictionaries are usually omitted.

Comparison of these data leads to the conclusion that the main meaning of lemma profesor in Serbo-Croatian is equivalent to lemma 'professor' in English. This main meaning is dispersed by structural derivation to several lemmas that are related to each other by prototypical definitions.

Morphological dictionary of Serbian and structural derivation

Morphological dictionary of Serbo-Croatian is being developed in the format that has been accepted in the frame of the network RELEX and it is used both for tagging, disambiguation and lemmatization of texts and as a preprocessor of text for the production of the tagged corpus of Serbian using system Intex [START_REF] Silberztein | Le dictionnaire électronique et analyse automatique de textes: Le systeme INTEX[END_REF]. As to the initial choice of lemmas, the morphological dictionary of Serbian has reproduced those from traditional dictionaries. A class code that precisely describes its inflectional properties by means of a regular expression has been associated to each of these lemmas. For instance, class N1 is associated to the noun profesor, and class N661 to the noun profesorka. The inflectional code N661 distinguishes lemma profesorka from, for instance, lemma slika 'picture', associated with code N612, by specifying the following features: there is no sibilarization in dative singular, the ending for the genitive plural is -i-instead of -a-, and for the vocative singular -a-instead of -o-.

The problem outlined in the section 2 poses a more complex question to the construction of the e-dictionary of Serbian [START_REF] Vitas | The Flexible Entry[END_REF]: Is it possible to assemble the results of the structural derivation in a complex lemma in a way that is similar to the description of the inflective characteristics, so that both in monolingual and bilingual Serbian dictionaries only one entry (e.g. 'professor') is listed with assigned codes that describe its derivational capability? From the point of view of the construction of the e-dictionary of simple lemmas, this problem can be solved in two ways. The first solution implies the construction of a complex lexical graph that would gather all the lemmas listed in Tables 1 and2. Such a lexical graph for the super-lemma profesor is represented in Figure 1.

In this lexical graph every string in the square brackets refers to the corresponding entry in the edictionary [START_REF] Vitas | Recent Results in Serbian Computational Lexicography[END_REF]. This method enables the reduction of all these lemmas to one canonic form and the establishment of appropriate relations between them. The application of this graph to lemmatization gives the results presented in Table 7. This approach has several drawbacks. First, some of these lemmas (profesorčina and profesoričin), though possible, are neither listed in [START_REF] Rmsmh | Rečnik srpskohrvatskoga književnog jezika[END_REF] nor have appeared in the corpus of Serbian. However, they have to be presented in the e-dictionary in order to be recognized by this lexical graph. Second, this graph is linked to the lemma 'professor', and not to the lexical class with its properties, and third, the lemma profesor is by no means an exception -the same properties apply to a large class of animate masculine nouns. Finally, as stated before the phenomena of structural derivation that are applicable to lemma profesor are not the only productive phenomena of this kind. Thus, another solution that makes use of the morphological grammars is being explored.

Morphological grammars

We have added a component in INTEX 4.30 that provides a different approach to the recognition of derived forms, by using morphological graphs that produce lexical constraints. [START_REF] Silberztein | INTEX Manual[END_REF]. The basic idea is to extrapolate the missing lemmas by transducers that model certain morphological processes and that are applied only to the entries already in the dictionary. Applied to the example we used this means that only one lemma, profesor, needs to be present in the morphological e-dictionary. The remaining lemmas recorded in traditional dictionaries, as well as those that are not recorded, can be described by transducers that represent a type of a formal morphological grammar.

For instance, Figure 2 represents the morphological graph that describes the structural derivation processes, such as derivation of possessive adjective, gender motion, diminutives, augmentatives, and relational adjectives from the masculine gender nouns. In the case of the possessive adjective, the noun it is derived from is assigned during the text processing as a lemma to recognized adjective forms and a syntactic property +Pos is added to it. The application of this graph enables searching with the pattern <N+Pos>, that retrieves from the text all the possessive adjectives derived from the nouns in the dictionary, which themselves need not be in a dictionary. Several lines from the concordances produced are given in Table 8. It should be noted here that this solution enables the recognition of all possessive adjectives derived from the nouns presented in e-dictionary, and not only the particular cases, such as profesorov.

Conclusion

We have shown in this paper that lemmas derived by structural derivation in Serbian can be recognized in text without being explicitly recorded in a dictionary. As a consequence it is possible to reorganize the complete inventory of lemmas in dictionaries of Serbian, both monolingual and multilingual. Finite state transducers enable a precise classification of processes of structural derivation in a way similar to the classification of inflective phenomena.

  NATO-a na Jugoslaviju, berlinski {profesori,profesor.N+Hum} posebno naglašavaju e boje neprijatnog znamenja ili -{profesorke,profesor.N+Hum+FG} ruskog jezika. ma i rasklimanim klupama, niskim {profesorskim,profesor.N+PosQ} platama, razuz nove u oblasti razmene studenata, {profesorskog,profesor.N+PosQ} kadra, naučni tek sada svestan važnosti {profesorskog,profesor.N+PosQ} zvanja i svih ku zahvalnost dugujemo pijanisti, {profesoru,profesor.N+Hum} Dušanu Trbojeviću Table 7: Lemmatization with the graph from Figure 1

Figure 2 :

 2 Figure 2: Graph of derivational class containing the lemma profesor

Table 1 :

 1 Lemma profesor and its derivatives in[START_REF] Rmsmh | Rečnik srpskohrvatskoga književnog jezika[END_REF]

			GRAMMATICAL DEFINITION	DEFINITIONS	FREQUENCI ES ON SRPCOR
	1 profesor	m	title of teacher ... and person that has that title	2197
	2	profesorica= profesorka	f	1. woman professor 2. wife of professor (profesorova žena)	-ica = 13 -ka = 212
	3 profesorski	-a,-o	1. that is related to professors 2. that is characteristic for professors	67
	4 profesorčić	m	dim. and pej. of professor	1

Table 3 :

 3 ). Some derivatives of lemma profesor not recorded in[START_REF] Rmsmh | Rečnik srpskohrvatskoga književnog jezika[END_REF]

			Unmarked inflection (N601)	profesorica (N651)	profesorka (N661)
	nom.sing.	žen-a 'woman'		profesoric-a	profesork-a
	voc.sing.	žen-o			profesoric-e	profesork-a
	gen.pl.	žen-a			profesoric-a	profesork-i
			Table 2: Inflectional properties of some feminine gender nouns
			Lemma	Grammatical definition		Definition	Frequencies on SrpCor
	5	profesorski	Adv	in the way of professor	2
	6	profesorov	AdjPoss	belonging to professor	20
	7	profesoričin	AdjPoss	belonging to (woman) professor	0
	8	profesorkin	AdjPoss	belonging to (woman) professor	2
	9	profesorčina	f (Gen = m)	augmentative of professor	0
				Slovenian		Serbo-Croatian
			Lemma	Grammatical definition	Translation
		profesor	-ja, m	profesor 'professor'
		profesorica	f		1. profesorica 'woman professor' 2. profesorka, profesorova žena
		profesorski	-a,-o	profesorski 'as a professor'

Table 4 :

 4 Lemma profesor and its derivatives in[START_REF] Jurančić | Slovensko srpskohrvatski rečnik, Državna založba[END_REF]

		(Serbo-)Croatian	English
	Lemma	Grammatical definition	Translation
	profesor	m	teacher, professor
	profesorica	f	(women 30 ) professor, professoress
	profesorka	f	see 16 profesorica
	profesorski	adj	teacher's, professor's, professorial

Table 5 :

 5 Lemma profesor and its derivatives in(Bujas, 2001)

	English	sense Croatian or Serbian
		1.	čovjek koji otvoreno iznosi svoje uvjerenje
			'man that overtly presents his believes'
		2.