Mickael Coustaty

Jean-Marc Ogier

Graph matching versus bag of graph: a comparative study for lettrines recognition

Keywords: Lettrine, Historical graphical documents, graph based representation, indexing

This paper proposes a comparison of three classi fication methods of graphical historical images. Historical image datasets are becoming bigger and bigger, and the use of classical computer vision techniques is not sufficient to deal with these large repositories. In the context of this paper, we propose to compare three methods by applying graph matching techniques on a dataset already used in many papers. The first one is based on a statistical approach, the second one on a graph-based classification, and finally the third one is an hybrid approach relying on the specificities of the two previous one. For this last method, we propose here to adapt it to this specific dataset. Some results are proposed and commented, what shows the superiority of the hybrid approach.

I. INT RODUCT ION AND CONTEXT

With the improvement of printing technology since the 15th century, a huge amount of printed documents have been published and distributed. Since that time, many of the books have been falling into decay and have been degraded by the time. Due to their intensive manipulation, the physical objects, i.e. books themselves, are in potential danger of extinction, as well as our cultural heritage. Therefore, there are a lot of attempts to keep, organize and restore ancient printed documents, in order to preserve these documents and their contents. As a consequence, many digitizing processes can be observed worldwide in many institutions, in order to protect physical objects from human degradation and in order to share historical information. However, even if digital era offers many opportunities, the digitized documents are not sufficient by themselves if one wants to offer the possibility to retrieve, navigate, and extract information from documents. Some dedicated tools using some document analysis and indexing process are needed.

Driven by rapidly changing amounts of digitized historical document, some specific pattern recognition systems have been defined. Indeed historical's document images, such as lettrines (decorative capital letters), are particularly hard to process into recognition scheme since they contain a lot of information (like texture, decorated background, letters). Figure 1 illustrates some samples of lettrines. One can remark that each image is a mixture of components such that the letter in the one hand and the background pattern on the other hand. In addition, some degradation linked to the state of original paper and the digitization can be observed. To deal with this kind of properties, pattern recognition systems require specific techniques which take into account these characteristics.

Many works tended to index and to search for similar complex historical images [1], and generally the results related to pattern recognition can be broadly divided into statistical and structural methods [START_REF] Bunke | Towards bridging the gap between statistical and structural pattern recognition: Two new concepts in graph matching[END_REF]. In the former, the document is represented by a feature vector [START_REF] Mehri | Texture feature evaluation for segmentation of historical document images[END_REF], [START_REF] Almazan | Word spotting and recognition with embedded attributes[END_REF], and in the latter, a data structure (e.g. graphs or trees) are used to describe objects and their relationships in the document [START_REF] Jouili | Hypergraph-based image retrieval for graph-based representation[END_REF], [START_REF] Raveaux | Structured representations in a content based image retrieval context[END_REF].

Examples of lettrine images

Finding a proper representation of objects is a key issue in pattern recognition and document analysis. Common ways of object representation generally rely on the use of statistical pattern recognition techniques (like features vectors) to sum marize the radiometric content of an image on one hand, or on the use of structural pattern recognition approaches to sum marize the topological organization of image's content (trees, graphs, ... ) on the other hand. Most of the recognition systems are limited to work with a statistical representation, mainly due to the need of computing distances between documents (feature vectors) or because of the necessity of finding a representative of a cluster of documents. When a numerical feature vector is used to represent the document, the structural information is generally discarded while the structural representation all wos to keep it. Structural representations are generally more powerful in terms of their representational abilities [START_REF] Bunke | Towards bridging the gap between statistical and structural pattern recognition: Two new concepts in graph matching[END_REF]. In a general comparison of these two approaches, we can observe that:

+

Features vectors have a low computational complexity and many algorithms are available

Features vectors have a limited representational power and the dimensionality is fixed, (i.e. all the images are reduced to the same quantity of information) + Graphs have a high representational power (mainly linked to their capacity to represent topological rela-1 tions) and a lot of flexibility as there are no initial limitations on graph size Graph matching techniques generally have a high computational complexity Since we deal with complex images (lettrines), the structural approaches seem to be more suitable for the representation task. Graph-based representation means to be able to compute a distance between two graphs. This can be done using some graph kernels techniques to reduce a graph to a feature vector or by using some graph matching techniques to compare the topology of these two graphs. In the specific case of lettrines, different works aimed at representing lettrines with graphs and computing some distances based on matching techniques [START_REF] Coustaty | Discrimination of old document images using their style[END_REF], [START_REF] Jouili | Hypergraph-based image retrieval for graph-based representation[END_REF]. A new idea, proposed in [START_REF] Silva | Bog: A new approach for graph matching[END_REF], aims at mixing the power of structural comparison techniques (graph matching techniques) with the bag of words model. We propose a comparison between these two recent works based on graphs in this paper.

II. METHODS COMPARED IN THIS STUDY

Based on graph-based representation of historical images, this paper proposes to compare three recent approaches using the same distance between graph. The first method uses a graph matching technique that compares the structural information of graphs, second one uses a bag of word model to statistically compare images, while the last one is hybrid as it relies on the use of Bag of Graphs (BoG), which is an adaptation of the Bag-of-Words model to graph domain [START_REF] Silva | Bog: A new approach for graph matching[END_REF].

The choice of these three methods relies on the fact that they use the Heterogeneous Euclidean Overlap Metric (HEOM) distance defined in [START_REF] Jouili | NAVIDOMASS: structural-based approaches towards handling historical documents[END_REF] to compute a distance between two graphs. This metric has proved its reliability for image recognition [START_REF] Jouili | Hypergraph-based image retrieval for graph-based representation[END_REF], [START_REF] Silva | Bog: A new approach for graph matching[END_REF]. Moreover, this distance between graphs keeps some information related to the structure of graphs by taking into account: Let i and j be the features vectors respectively linked to the ith and the lh node. A node signature distance based on the HEOM which handles numeric and symbolic attributes can be defined by the function HEOM(i,j):

A HEOM(i,j) = L O(ia,ja) 2 (1) 0<=0
where ex refers to one attributes of A and o(ia,ja) is defined as:

if ia or ja is missing if ex is symbolic if ex is numeric (2)
Starting from this distance, it then becomes possible to compute a distance between nodes of graph, and a graph matching technique or a statistical classification process can be applied to compare images. We selected three methods that complement each other to evaluate the performance of structural and statistical approaches. The first one, which is structural [START_REF] Jouili | NAVIDOMASS: structural-based approaches towards handling historical documents[END_REF] is a graph-based approach, while the second one, which is statistic, mimics the bag of visual words models [START_REF] Silva | Bog: A new approach for graph matching[END_REF]. Finally, the third one is an hybrid one which uses the HEOM distance in a Bag of Visual Words model.

A. Graph-based approach

Classically, graph-based approaches rely on the use of matching techniques to check if two graphs are similar, i.e. they share the same structural representation. Many works were done in this field to find similarities between graphs with different techniques. We can cite some recent works that used a vectorial representation for the indexing of structural Informations [START_REF] Sidere | A vectorial representation for the indexation of structural informations[END_REF], that extracted some features from graph to summarize their content with a fuzzy multilevel graph embedding [11] or a family of methods that tried to evaluate the distance between graphs by minimizing edit distance. This last means counting the least cost of edit operations needed to make two graphs isomorphic. A standard set of edit operations is given by insertions, deletions and substitutions. These edit operations are applied on both edges and nodes. In addition, a certain cost is associated with each of these operations. Obviously, for every pair of graphs A and B there exists different sequences of edit operations transforming A into B. However, the computation of the edit distance between two graphs involves not only finding a sequence of edit operations to transform one graph to the other, but also finding such a sequence that possesses the minimum total cost. Formally, The graph edit distance between two graphs A and B is given by: E ,,((A,B) i=l [START_REF] Mehri | Texture feature evaluation for segmentation of historical document images[END_REF] where ,(A, B) denotes the sequences of edit operations transforming A into B and c( ei) denotes the cost of the edit operation ei. In order to compute an optimal graph edit distance, several techniques have been proposed. In this paper, we consider an improvement of the approximation of graph edit distance based on [START_REF] Jouili | Graph matching based on node signatures[END_REF], [START_REF] Jouili | NAVIDOMASS: structural-based approaches towards handling historical documents[END_REF] using the HEOM.

d(A,B) k min L c(ei) (el, .,ek)

B. Bag of visual words

The second method evaluated in this paper is described in [START_REF] Coustaty | Discrimination of old document images using their style[END_REF] and relies on a widespread approach of the literature: the bag of words (BoW) model [l3], [START_REF] Sivic | Efficient visual search of videos cast as text retrieval[END_REF]. This model [START_REF] Baeza-Yates | Modern Iriformation Retrieval[END_REF] was originally designed for text classification and retrieval. Its main idea is to represent each text by a vector that counts the occurrences of words in the document. The similarity between two texts is evaluated based on the similarity of their words distribution. The BoW model has been used in different domains and adapted to the natural image analysis with the introduction of Bag of Visual Words (BoVW) [START_REF] Sivic | Discov ering objects and their location in images[END_REF], [START_REF] Nguyen | Multi-modal and cross-modal for lecture videos retrieval[END_REF]. We also adapted it to historical images in [START_REF] Nguyen | Bags of strokes based approach for classification and indexing of drop caps[END_REF] where visual words where extracted using 3 * 3 patterns defined in [START_REF] Coustaty | Towards historical document indexing: extraction of drop cap letters[END_REF].

Based on this principle, this approach combines the use of the Zipf law and the use of bag of patterns, in order to identify the most important 3 * 3 patterns for each image. In fact, each image is described by a vector that contains the list of most interesting patterns. This selection however involves different sizes of vector, and different features in vectors. A similarity measure between images (ie. vectors) was defined to compare images. This measure between two vectors (VI and V 2 ) relies on a series of three values.

1)

Length Ratio: RL 2)

Similarity Ratio: Rs 3)

Pattern Distance: DPatt

The two first ratios indicate the similarity between two vectors.

RL and Rs have a value E [0; 1], with 0 corresponding to dis similar vectors, while 1 indicates a perfect similarity between them. On the other hand, the pattern distance correspond to an euclidean distance. This means that the smaller the distance is, the closer the vectors are (and vice-versa). These three values are combined into a global similarity measure. Considering two images il and i 2 , the measure is defined as:

C. Hybrid approach Finally, the last approach presented is hybrid since it relies on the use of Bag of Graphs (BoG), which is an adaptation of the Bag-of-Words model to graph domain. In this approach, the local structures of a graph are described by node signatures and each graph is represented as a bag of node signatures. The graph matching problem is then reduced to the problem of computing the similarity between feature vectors like in the classical bag of words method. We decided to use the HEOM distance to compare nodes as it allows keeping structural information of graph. Moreover, we used the euclidean distance to compare two feature vectors, but any other distance (like the Manhattan or the Earth Mover's distance) could be used in this last step.

The BoG approach is a two-steps process that performs graph classification and graph retrieval. First, a learning phase generates the code book used for the bag representations, and in the second phase, the graph classification process consists in computing an euclidean distance between a query and all the graphs in the database as they are reduced to a feature vector. The class of the most similar histogram allows deducing the class of the query. To generate the codebook, we take all the nodes of graphs with their local features (see below for details) and we input them in a clustering algorithm to compute some nodes' prototypes.

The local features of a vertice used for the bag representa tion relies on features associated to the node itself, but also to its neighborhood. More formally, let G = (V, E) be a graph composed of a set of vertices V and a set of edges E, Av the set of attributes (numeric or symbolic) related to the vertices, AE the attributes (numeric or symbolic) related to the edges and Di the degree of vertice Vi' The node signature NoS of Vi corresponds to the list of these information and can be defined as follows:

(4)

where AEi D corresponds to the set of attributes of edges linked to the node (AEil; ... ; AEi D ). This set is sorted in order of increasing values to ensure a consistency when comparing two node signatures.

We also assume that graphs correspond to a segmentation process, and that each node corresponds to a region in the image. We thus propose to use the following features for node's description: X and Y coordinates, area and eccentricity. To describe edges with the following set of features: the distance between region centroids, the degree of the neighbor node and the orientation of the edge. Finally, we apply the Mean Shift algorithm [START_REF] Comaniciu | Mean shift: a robust approach toward feature space analysis[END_REF] to create the codebook in the learning phase. The use of an unsupervised clustering method, like Mean Shift, simplifies the process of building the dictionary. Starting from this codebook, each node of the graphs is associated to a cluster, and each graph is then described by an histogram of nodes' prototypes. Now that we have presented the methods, we present the dataset used to compare these approaches and to discuss on the performances and the differences between them.

III. EXPERIMENTAL RESULTS

A. Lettrines in details

Lettrines are particularly difficult images (images degraded by time in black and white) and many works tried to recognize them using some statistical and structural approaches [START_REF] Pareti | Ancient initial letters indexing[END_REF], [START_REF] Coustaty | Discrimination of old document images using their style[END_REF]. We decided to use the dataset of these papers to compare these methods and to propose an objective evaluation. It contains more than 300 images coming from the Centre dEtudes Superieur de la Renaissance of Tours, France. Images from this database have been labeled by experts who indicated the style of the lettrine. The three main styles are presented in figure 2. As one can see on figure 1, lettrines are made up of two principal elements: the letter and the background. These elements are used by historians to retrieve similar lettrines in order to identify the printer and the period. This paper proposes to compare different methods to identify the style of the background. In order to be able to identify the style with graph-based approaches, we extracted regions of interest from lettrines and described them with graphs. Our aim is to extract some meaningful region that correspond to pure geometrical component. For this, in [START_REF] Coustaty | Towards historical document indexing: extraction of drop cap letters[END_REF], authors propose a decomposition model which splits an image into three components: the first one, u, containing the structure of the image (see Figure 3(b) for an example), a second one, v, the texture, and the third one, W, the noise. For better comprehension of differents spaces, see [START_REF] Aujol | Structure-texture image decomposition -modeling, algorithms, and parameter selection[END_REF]. We are particularly interested by the first one which capture region with low variation of greylevels, that represent the meaningful regions. From this image, we apply a Zipf law, a three steps process, to extract regions of interest:

• Simplification of image applying a 3-means on grey level histogram to reduce number of patterns (the choice of three can be explained by the fact that images are composed of three elements : background, foreground, motif)

• Seek for patterns the size of which is 3 by 3 to obtain their frequency and their rank (that can be resume to a count of each pattern that permit to know their frequency and their rank) Once shapes have been extracted, one can seek connected components of binarized image. When observing all the con nected components in Figure 3(c), we can see that the most important shapes have particular characteristics (based on size, location, center of mass and exccentricity). A selection of connected components in accordance with these parameters permit to obtain region of interest of drop caps. An exmaple of extracted connected components can be seen in Figure 3(d).

From all these extracted shapes, we build a graph where nodes correspond to region of interest. Each node is described by a quadruplet of information which contain the coordinate of the center of mass, area and eccentricity of each shape. An illustration of this last process is presented in figure 4. An example of graph extracted after the segmentation process

B. Evaluation protocol

As presented before, the methods presented rely on a training phase and a recognition phase. For this evaluation, We used 10 images by style (ie. class) in the learning step (l3% of all database images), and the rest for the recognition step. For all images, the distance between the image and all the others of the database are computed using the HEOM metric for methods 1 and 3, while the "Pattern metric" was used for the second work. We then used a k-nearest neighbour (k-NN) classifier to class each image in a style. The obtained results are summarized in table I.

C. Results and discussions

We computed all these methods on the dataset and we obtain the results presented in table I. These results correspond to the accuracy of our system to identify the good style. It can be seen as the Precision of our system with only 1 result returned for each query (Precision@I).

ACCURACY COMPARISON BETWEEN STATISTICAL AND STRUCT URAL APPROACHES

First of all, we can see that the graph matching and the bag of visual patterns provided very similar results and that it is quite difficult to recognize more than 70% of the dataset with previous works. We can particularly see that the statistical based approach got better results with the class "Style 2". This can be explained by the fact that this class is mainly composed of lettrines with a white background, small flowers and the letter. Statistically, it is easier to retrieve images with the same proportion of patterns, while the regions extracted and put in the graphs are not always the same. One solution that could be considered will be to compute more features for the regions and to add them into the graph matching system. However, adding more complex features will imply higher computation time and it could be difficult to retrieve similar regions that are not only composed of white (regions composed of textures).

Regarding the bag of graph approach, which corresponds to the most recent work, it seems to globally present better results. The main drawback of this approach is that it relies on the mean-shift algorithm to define the node clusters in the learning phase. As in this work we limited to 10% this stage, we can see that the system is not able to correctly define some prototypes for all the classes (style 2 is never recognized). At the opposite, the results obtained for style 1 and 3 are the best of this evaluation. Finally, we can notice that the last method mixes some statistical and structural approaches, and that this combination of information clearly enhance the results by 10% A perspective of this work is to evaluate the difference be tween these approaches regarding the algorithmic complexity, and thus its computation time. Actually, the dataset involved is quite limited (obtaining a larger annotated dataset of historical document is quite difficult) and all these methods computed the results in an equivalent duration (about 15 seconds to classify all the dataset). This similarity is mainly due to the fact that lettrines are represented with small graphs (15 nodes in gen eral). In that configuration, computing the matching between all graphs is quite similar to the computation of a clustering algorithm and the computation of histogram distances between images. However, we have to notice that this computation time do not take into account the pre-processing techniques which consisted in the graph generation in the structural of hybrid approach, while the statistical approach (Bag of Visual Patterns) starts from the original images.

IV. CONCLUSION AND PERSPECTIVES

In this paper we propose a comparative study of three methods applied on historical images: a statistical, a struc tural and an hybrid approach. We used a well-know dataset of historical images to compare these methods and we can conclude that the hybrid one take advantage of this mix and obtain better results. The next step of this work will be to extend the dataset in order to compare these approaches not only on historical documents but more generally to documents. Another promising issue could be to propose a combination of these classification process as each classification technique has its own errors different from the others.

Fig

  Fig. 1.Examples of lettrine images

•

  the attribute of the node n( exi • the degree of ni: B(ni) • the degrees set of the nodes adjacent to ni: {B( ni) }liijEE • the attributes set of the incident edges to ni {,Bij hijE E

Fig. 2 .

 2 Fig. 2. Examples of lettrines for each style present in the database used in [21]. Style 1 correspond to lettrines composed of hashed background, style 2 contains lettrines with white and decorative background, and style 3 lettrine with a black background with white dot

•

  Classification of patterns according to the evolution law of the frequency compared to their rank. From the precedent step, three straight lines are computed to estimate the main parameters of Zipf laws that in terfere. The first one corresponds to the most frequent patterns (shapes of image) and an example of result is presented in Figure.

Fig. 3 .

 3 Fig. 3. Example of an image and representation of different treatments: a) Original image; b) Region with low variation of greylevels; c) Shapes segmented using Zipf law (in black); d) Six larger connected component

Fig. 4 .

 4 Fig. 4.An example of graph extracted after the segmentation process

TABLE I .

 I

ACKNOWLEDGMENT

We wish to thank Jonathan LOMBARD, Valentin FAV REAU and Hassan GUINALE for their help in the im plementation of the hybrid method.


Hanen Khlif
email: hanen.khlif89@gmail.com

Sophea Prum
email: sopheaprum@gmail.com

Yousri Kessentini
email: yousri.kessentini@gmail.com

Slim Kanoun
email: slim.kanoun@gmail.com

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

Fusion of explicit segmentation based system and segmentation-free based system for on-line Arabic handwritten word recognition

Keywords: line handwriting Arabic word recognition segmentation free, analytical approach, HMM, SVM, information fusion, I

The complexity and viariability of the Arabic handwriting makes difficult the implementation of an efficient recognition system through the use of a unique recognition engine.. In this paper, two handwriting word recognition systems are combined in order to take advantage of their complementarities. The first one is a segmentation free based system that uses the generative classifier HMM. The second system is discriminative based. Relying on analytical approach, it proceeds with explicit segmentation of words into graphemes. Different combination strategies are compared including sum, product, Borda count and Dempster-Shafer rules. The experimental results conducted on ADAB database demonstrate a significant improvement of recognition accuracy of 5% compared to the segmentation free based system and 9% compared to the analytical based system.

INTRODUCTION

This paper deals with on-line Arabic handwriting recognition system, which becomes a fundamental service in our modern society. Handwriting recognition can be defined as the process of transforming text represented in the spatial form into its symbolic representation [START_REF] Rabiner | A tutorial on Hidden Markov Models and selected applications in speech recognition[END_REF] In the literature, handwriting recognition can be divided in two categories, depending on the nature of the input. First, off-line recognition which is essentially based on the treatment of texts that are generally captured by scanned images; and on-line recognition which is generally based on digital pens or tablets, for which a chronological sequence of coordinates is usually produced. The set of sequences represents a pen movement that can scale on the mapped screen surface. This mapping (time, coordinates and sequence) is captured in a real-time. As a consequence, online handwriting recognition technology has a great potential for improving human machine interaction.

Over the past few years, many techniques have been proposed in the literature. There are a huge number of researches which have dealt with Latin and Chinese handwriting recognition. However, only a few of these researches have considered Arabic language.

In Arabic language, words are written in a cursive style, from the right to the left. There is no discreet type of handwriting. In addition, each letter can be written in four different shapes according to its positions in the word. Furthermore, the Arabic language contains some diacritics, hence reversing or even changing word meaning by a simple sign change. Consequently, handling such a complex script with large lexicon is a challenging task for existing handwriting recognition systems.

Two approaches have been used for handwritten word recognition [START_REF] Burrow | Arabic handwriting recognition[END_REF]: the global approach that considers each word as a class [START_REF] Amin | Handwriting written Arabic character recognition by the IRAC system[END_REF][START_REF] Saabni | Hierarchical on-line Arabic handwriting recognition[END_REF][START_REF] Razzak | Locally baseline detection for online Arabic script based languages character recognition[END_REF] and the analytic approach that involves segmentation and recognition processes to determine the sequence of characters forming the input word [START_REF] Razzak | Locally baseline detection for online Arabic script based languages character recognition[END_REF][START_REF] Abdelaziz | Large Vocabulary Arabic Online Handwriting Recognition System[END_REF][START_REF] Daifallah | Recognition-based segmentation algorithm for on-line Arabic handwriting[END_REF][START_REF] Izadi | Online Writer-Independent Character Recognition Using a Novel Relational Context Representation[END_REF].

A recent survey on on-line Arabic handwritten recognition has been presented in [START_REF] Tagougui | Online arabic handwriting recognition: a survey[END_REF]. A segmentation-based recognition method operating at a stroke level and having Segmentation Points (SPs) has been proposed in [START_REF] Daifallah | Recognition-based segmentation algorithm for on-line Arabic handwriting[END_REF] in the context of online cursive handwritten word recognition system. The authors have used first an algorithm that works at stroke level by segmenting it into letters. Then, HMM is used to classify the sub-strokes to letters using the Hu features. The letters candidates and their scoring have been used to determine the best set of SPs. In [START_REF] Elanwar | Unconstrained arabic online handwritten words segmentation using new hmm state design[END_REF], the authors have proposed two stages for the on-line Arabic handwritten text segmentation system based on Hidden Markov Model (HMM). In the first stage, SPs were nominated before being validated in the second stage, using a rule-based engine. The system has been experimented on a self-collected database named OHASD. In [START_REF] Abdelazeem | On-line arabic handwritten personal names recognition system based on hmm[END_REF], the authors have designed a system for Arabic personal names based on HMM and trained with the ADAB-database using two different methods: manually segmented characters and non-segmented words. In [START_REF] Biadsy | Segmentation-free online arabic handwriting recognition[END_REF], a combination of HMM and sliding window have been used to recognize Arabic word with three features (the local angle, super segment, and loop presence). In [START_REF] Izadi | Online Writer-Independent Character Recognition Using a Novel Relational Context Representation[END_REF], the authors have presented a system of character recognition based on support vector machine (SVM) and using a new feature called relative context (RC). RC was obtained from the relative pairwise distances and the angles of the writing trajectory.

From the above review, it can observe that there are many on-line Arabic handwriting recognition systems with different classification techniques and feature extraction methods. However, it is noticed that many researchers have found appropriate combinations of different classifiers aiming at providing better recognition results. Generally, there are two main categories of approach for information combination: feature combination representation and decision fusion based approach. The first approach joins 1 different features before using the classifier. The method of the second approach is based on the combination of decisions independently of the different information sources. Among the methods we can cite majority vote [START_REF] Kimura | Handwritten numerical recognition based on multiple algorithms[END_REF], borda count [START_REF] Wang | Combination of multiple classifiers for handwritten word recognition[END_REF], linear combination of the confidence value [START_REF] Hashem | Improving model accuracy using optimal linear combinations of trained neural networks[END_REF], and Dempster Shafer theory [START_REF] Kessentini | A Demspter-Shafer Theory basedcombination of Handwriting Recognition Systems with multiple rejection strategies[END_REF].

In this work, an information fusion of the two different analytical systems is proposed to build an online Arabic handwritten word recognition system. These two systems are combined in order to take advantage of their complementarities. First, they use different segmentation methods. The first system relies on segmentation-free strategy while the second system relies on explicit segmentation using segmentation/recognition strategy. Secondly, these systems rely on different classifier. The first system relies on generative HMM model while the second system relies on discriminative SVM classifier. Thirdly, these systems use complementary methods for extraction features. The first system relies on local on-line features extracted from each point of the input signal while the second system relies on the combination of on-line and offline features. The detail presentation of these methods is presented in section II. and III. Respectively

The rest of this paper will be organized as follows. Section II presents the first system relying on a segmentation free approach. Section III presents the second system on analytical approach. Section IV introduces the combination methods which allow the fusion of the output of both systems. Ultimately, the experimental results are revealed in section V.

II. SYSTEM BASED ON SEGMENTATION FREE APPROACH

The First system relies on segmentation free approach with a generative classifier HMM. The architecture of this system is illustrated in Fig. 1. First, the preprocessing phase is used to reduce the effect of the handwriting device noise and the handwriting irregularity. Then, numerous features are extracted from the preprocessed handwriting signal and are used to train the HMM models in the training step. Afterwards, an embedded training phase is introduced. Finally, a recognition phase where handwriting input is decoded and recognized using the training output. The output of system is the top scoring hypotheses of the handwriting input. In the following sub-sections, each component of this system will be detailed.

A. Preprocessing

Preprocessing is the first step to recognize words in the suggested system. Given the input handwriting signal, the preprocessing method is applied in order to remove the noise caused by the acquisition device and normalize the online signal respecting the writer's speed. In this system, four commonly used methods (size normalization, interpolation, smoothing and resampling) are applied.

B. Feature extraction

Feature extraction is a very important process in the general problem of classification and handwriting recognition. It consists in extracting the measures of the entries to differentiate classes. In this system, from each point of the input signal, a vector of 7 features is extracted: (coordinates, direction, curvature, Pen Down or Pen Up). These features can be classified as temporal features, directional features and curvature features, as presented in the following paragraphs 1) Temporal Features: First, an online signal is represented by a sequence of points P(x (t), y (t)), where t represents time. The sequential nature of the information acquired by the tablet is preserved to provide a better recognition rate. At this level, different parameters of the pen status are detected: horizontal position x (t), the vertical position y (t) and the time t. Then, to specify the state of the pen at a point , the information of pen's movements is detected (pen-up and pen-down) and allows to define a new feature or a new point at the character level.

2) Directional Features: this method consists in extracting local writing direction features at each point P(t) = (x (t), y (t)) at instant (t). This method has been described in [START_REF] Jaeger | Online handwriting recognition: the NPen++ recognizer[END_REF]. For each point P(t), cosinus and sinus of writing direction angle are extracted as follows:

Where , and are defined as follows:

3) Curvature Features: The curvature at point (x (t), y (t)) is represented by the cosinus and sinus of the angle Ɏ defined by the following three points [START_REF] Jaeger | Online handwriting recognition: the NPen++ recognizer[END_REF]:

(x (t-2), y (t-2)), (x (t), y (t)), (x (t+2), y (t+2))

The features (cos(Ɏ) and sin(Ɏ)) can be computed by: cos Ɏ =cos (t-1)*cos (t+1) sin (t-1)*sin (t+1) sin Ɏ =cos (t-1)*sin (t+1) sin (t-1)*cos (t+1)

C. HMM Training

After the preprocessing and feature extraction phases, this step consists in creating (training) HMM model for each character class. In the proposed system, a left to right HMM is considered. As mentioned earlier, the shape of each Arabic character is changed according to its position in the word. Therefore, to represent the 28 Arabic characters in different positions in a word (beginning, middle, end word position), there are HMMs for 69 unique models. Each character model is composed of 5 emitting states. The Gaussian Mixtures (6 per state) are used to model the observation probabilities. An embedded training with Baum-Welch algorithm is applied on word examples where all character models are trained in parallel. The system builds a word HMM by the concatenation of the character HMM corresponding to the word transcription of the training sample.

D. HMM decoding

In the recognition phase, features vectors extracted from a word image are passed to a network of lexicon entries formed of words HMM built by the concatenation of their character HMM. The character sequence providing the maximum likelihood identifies the recognized entry. Word recognition is achieved with the Viterbi algorithm.

The overall recognition process is presented in Fig. 2. The second system relies on explicit grapheme segmentation and SVM-based single character recognition. Word recognition is achieved with an efficient dynamic programming method similar to the Viterbi algorithm. This system has been used for on-line handwritten word recognition for English and French languages that rely on Latin character set. The details of this system are presented in [START_REF] Prum | A Discriminative Approach to On-Line Handwriting Recognition Using Bicharacter Models[END_REF].

The global view of this system is illustrated in Fig. 3. More specifically, given an input handwritten signal, preprocessing methods are applied. For a fair comparison with the HMM-based system, the same pre-processing methods are used (see Section II). The normalized signal is then segmented into a set of graphemes to be further used to create a lattice of L levels. Each node of the lattice is considered as a candidate character. For each node of the lattice, a set of on-line and off-line features are extracted. Next, a single character recognizer is used to emit recognition hypotheses for each node. In the last stage, a word decoding process is used to find the most probable words.

A. Segmentation and lattice creation

The normalized signal (resulting from the previous step) is over-segmented into a set of graphemes. In the suggested system, a grapheme is defined as the set of all the consecutive points of a given stroke located between a local minimum and a local maximum (following the y coordinate)

These segmented graphemes are used to create a lattice of levels which represents all the possible concatenations of graphemes [START_REF] Prum | A Discriminative Approach to On-Line Handwriting Recognition Using Bicharacter Models[END_REF]. A node in the lattice may be a grapheme or a concatenation of graphemes. Each node is considered as a candidate to be a character and is therefore introduced as the input of the single character recognizer whose role is to generate character hypothesis of each node.

B. Feature extraction

In order to benefit from the advantages and complementarity of different feature extraction methods, this system uses the combination of on-line features and off-line features. From the input on-line signal (the signal containing in each node), a set of on-line features, mainly inspired by [START_REF] Anquetil | Mod ғ elisation et Reconnaissance par la Logique Floue : Application `a la Lecture Automatique En-ligne de l'Ecriture Manuscrite Omni-scripteur[END_REF], are extracted. These features represents the number of strokes, the information of starting and ending points of the signal (x, y coordinates, gradients at the starting and ending points).

The off-line features can be computed from the image generated artificially by connecting the consecutive points in the input signal. Nine families of off-line described statistical and structural features are used. These features consist in 5 families of global features (Hu invariant moments, projection, profile, Zernike and Radon moments) and 4 families of local features (intersection with straight lines, local extrema, points/junctions and holes and concave arc). These off-line features have been successfully used for offline character recognition problem [START_REF] Heutte | A Struc-tural/Statistical Feature Based Vector for Handwritten Character Recognition[END_REF] and other pattern recognition problems [START_REF] Menotti | ғ avez. Hu and Zernike Mo-ments for Sign Language Recognition[END_REF].

In total, a set of 254 features is obtained. This large set of features may contain some insignificant features, as well as some redundant features. This kind of features may increase the computational time, and sometime degrade the effectiveness of the classification system. In order to circumvent these problems, the Sequential Forward Floating Search (SFFS) Feature Selection method is used to reduce the size of this vector by removing the insignificant features. The detail description of these features is presented in [START_REF] Prum | On the use of a discriminant approach for handwritten word recognition based on bi-character models[END_REF].

C. Single character recognition system (SCR)

Support Vector Machine (SVM) is used as the discriminative classifier to crate our SCR. As mentioned earlier, the Arabic language is composed of 28 standard character classes. However, the shape of each character changes according to its position (start, middle, ending and isolated) in the word. Therefore, there is a high variation of shape in each class which will decrease the classification performance. To deal with this problem, characters can be categorized in 4 classes according to their position in the word: start-characters, middle-characters, ending-characters and isolated-characters.

Nevertheless, it is worth mentioning that this SCR is used to recognize each node in the lattice. In fact, it can be specified in advance if each node situates at the beginning, in the middle or at the end of the input word, according to its position in the lattice. Yet, it cannot be known in advance if each node is an isolated character or not. For these reasons, three different SCR systems are to be created. The first SCR considers the starting and isolated-characters (50 classes) and is used to recognize nodes at the beginning of the lattice. The second SCR considers the middle and isolated-character (61 classes) and is used to recognize the node and the middle of the lattice. The third classifier considers the ending and isolated-characters (58 classes) and is used to recognize the character at the end of the lattice.

D. Word decoding

Given a lattice G of graphemes corresponding to a word to be recognized, the word decoding step consists in searching an optimal path for each word [START_REF] Prum | On the use of a discriminant approach for handwritten word recognition based on bi-character models[END_REF] in a given lexicon, and calculating its recognition score. This word decoding process relies on dynamic programming.

IV. FUSION OF EXPLICIT SEGMENTATION BASED SYSTEM AND SEGMENTATION-FREE BASED SYSTEM

This section presents the proposed methods used to information fusion of systems based on segmentation free and analytical approach. As presented in the previous section, these two systems rely on different segmentation methods, feature extraction methods and classifiers. The goal is to combine the outputs of these systems in the best way in order to take advantage of the complementarities of these two systems.

The first step consists in selecting top N recognized words given by segmentation free and analytical based systems. Then, both outputs are combined together using different methods to deliver the new score for each word hypotheses. Finally, the list of hypotheses is sorted to have the list of the TOP N best classes as shown in Fig. To achieve this, we apply the following combination rules:

• Simple combination rules: sum and product rules to find the separate combination function for each class

• The rank-based combination methods: Borda count represents the combinations of medium, since the calculating rank requires comparing the original score with other scores produced during the same identification trial. The final output label for a given test pattern n is the class with the highest rank sum [START_REF] Kessentini | Constructing dynamic frames of discernment in cases of large number of classes[END_REF] • DST (Dempster-Shafer theory) aims at combining the classifiers we have presented in a previous work [START_REF] Kessentini | A Demspter-Shafer Theory basedcombination of Handwriting Recognition Systems with multiple rejection strategies[END_REF][START_REF] Kessentini | Constructing dynamic frames of discernment in cases of large number of classes[END_REF][START_REF] Burger | Dempster-Shafer based rejection strategy for handwritten word recognition[END_REF]. It consists in different step: First, for each of the Q classifiers, the likelihoods are normalized so that they sum up to one over the whole set of classes. Second, a mass function is derived from each of the Q classifiers. Third, the accuracy rates of the classifiers (derived from a cross validation procedure) are used to weigh each mass function in relation to the reliability of each classifier. Fourth, the Q mass functions are combined together. Finally, a probabilistic transform is applied, and the so-derived probability values are sorted decreasingly to provide the TOP N list. More details can be found in [START_REF] Kessentini | Constructing dynamic frames of discernment in cases of large number of classes[END_REF], [START_REF] Burger | Dempster-Shafer based rejection strategy for handwritten word recognition[END_REF] V. EXPERIMENTS AND ANALYSIS

The systems based on segmentation free and the analytical approaches are evaluated against other state of art HRW systems. There are applied using ADAB database of Tunisian town names. It comprises around 11024 samples written by more than 170 different writers divided to 4 sets.

El Abed et al. [START_REF] El Abed | On-line arabic handwriting recognition competition[END_REF] held the first competition on ADAB database at 10th International Conference on Document Analysis and Recognition (ICDAR), three data sets were provided for training (sets 1, 2 and 3) and set 4 was used for testing the systems. The results of set 4 for all the competing systems are shown in Table1. Our experimentation using ADAB where 8024 samples are used for training and 3000 are used for testing with a lexicon constituted of 706 words is shown in Table II andTable III. We evaluate 2 different groups of operations which are:

• Testing individual systems separately.

• Testing the different fusion methods: the sum rule, product rule, Borda count and DST.

The recognition rate given by the system based on analytical approach is 81,33% while the one given by the system based on segmentation free approach is 85,3% on the same test dataset. The best recognition rate is obtained by using the Borda count and DST that give a gain of 5% compared to the system based on segmentation free approach and 9% compared with the system based on analytical approach. Besides, it is observed that the sum and product rules give a more interesting result than individual systems. But the most important thing is that all combination rules improve the performance system.

To evaluate our systems with the stat of the art, we are testing individual systems and the different fusion methods in the same condition of competing systems in ICDAR 2009. From the results shown in Table I and Table VI, we can see how encouraging our system performance compared to the state of the art systems. Results show that the complementarities between both systems improve results because of the use of different characteristics (Offline that treat generally the form and Online that treat the trajectory of the signal). However, we can see that the treatment of Delayed Strokes is a messing operation in the system that can ameliorate the recognition rate.

The following figure presents different examples in which the global system using the combination provides a correct recognition while one of the combined systems fails to recognize a word. Fig. 5(a) shows that the system based on segmentation free approach cannot distinguish between «ϦΤΗ» and « « ϞόΣ» because of the similarity between the two characters differing in the occlusion. In the second example the letter «Ύϧ» is considered as « ήΑ » and « ήΑ » as « Ύϣ », hence highlighting the influence of diacritics processing performed by the system without removing them. With the system based on analytical approach Fig. In this paper the outputs of the system based on segmentation free approach and the one based on analytical approach for Arabic on-line handwritten word recognition have been combined. Four of the existing methods (sum rule, product rule, Borda count and DST) are used to combine both systems. The recognition rate achieved by this information fusion by any of these combination methods is much better than the recognition rate given by any of the individual systems used solely.

In this work, the fact that the information fusion with different features improves the final recognition accuracy has been demonstrated. This work can be extended to a combination which takes into consideration the decision of the system based on segmentation free approach depending on the confidence score obtained from the system based on analytical approach. Thus, the best accuracy can be reached to increase word recognition rate.

Figure 1 .

 1 Figure 1. Architecture of system based on segmentation free approach

Figure 2 .

 2 Figure 2. Handwriting word recognition scheme using HMM

Figure 3 .

 3 Figure 3. Global overview of the system based on analytical approach

4

 4

Figure 4 .

 4 Figure 4. Fusion of explicit segmentation based system and segmentationfree based system

  5(b), recognition errors come from segmentation errors.

Figure 5 .

 5 Figure 5. Examples of samples corrected recognitionally by the combination methods and confused by the individuals systems

TABLE I .

 I ADAB SET4 RESULTS(ICDAR 2009)

	System	Method	Top 1 Top 5 Top 10
	MDLSTM-1	NeuralNet 95.70 98.93 100
	MDLSTM-2	NeuralNet 95.70 98.93 100
	VisionObjects-1 NeuralNet 98.99 100	100
	VisionObjects-2 NeuralNet 98.99 100	100
	REGIM-HTK	HMM	52.67 63.44 64.52
	REGIM-Cv	VC	13.99 31.18 37.63
	REGIM-CvHTK HMM&VC 38.71 59.07 69.89
	TABLE II. ANALATYCAL AND SEGMONTATION FREE APPROACHES RECOGNITION RATE OF SYSTEMS BASED ON
	Recognition
	Approach	Method	Top 1	Top 5 Top 10
	Analytical		81.33% 86.86% 89.43%
	approach	SVM
	Segmentation		85.30% 91.26% 93.33%
	free approach	HMM

TABLE III

 III

	FUSION	.	RECOGNITION RATE OF THE INFORMATION
		Information Fusion
			Methods	Top 1	Top 5	Top 10
		Sum Rule	87.90%	92.46%	92.73%
		Product Rule	87.60%	92.46%	92.73%
		DST		90.26%	95.33%	95.77%
		Borda Count	90.30%	93.10%	93.6%

TABLE IV

 IV

	.	RECOGNITION RATE WITH ADAB SET4
	Recognition methods	Top 1	Top 5	Top 10
	SVM		66.8	80.5	83.1
	HMM	80.1	92,3	94.1
	Sum Rule	81.4	87.5	88.1
	Product Rule	81.4	87.5	88.1
	DST		83.9	92.8	93
	Borda Count	81.4	87.5	88.1


Nibal Nayef
email: nibal.nayef@univ-lr.fr

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

Semantic Text Detection in Born-digital Images via Fully Convolutional Networks

Traditional layout analysis methods cannot be easily adapted to born-digital images which carry properties from both regular document images and natural scene images. One layout approach for analyzing born-digital images is to separate the text layer from the graphics layer before further analyzing any of them. In this paper, we propose a method for detecting text regions in such images by casting the detection problem as a semantic object segmentation problem. The text classification is done in a holistic approach using fully convolutional networks where the full image is fed as input to the network and the output is a pixel heat map of the same input image size. This solves the problem of low resolution images, and the variability of text scale within one image. It also eliminates the need for finding interest points, candidate text locations or low level components. The experimental evaluation of our method on the ICDAR 2013 dataset shows that our method outperforms stateof-the-art methods. The detected text regions also allow flexibility to later apply methods for finding text components at character, word or textline levels in different orientations.

I. INTRODUCTION

There is a huge growth in the amount of multimedia data on social network media such as advertisements, holiday pictures, business cards, magazines. This has led to large data collections of heterogeneous and weakly structured content. Two popular types of images in network media are scene images with embedded text and born-digital images. Analyzing the latter class of images has not received as much attention as scene text images despite its importance. Analyzing the contents of such images is very challenging because of cluttered background, complex layout with mixed graphics and text, low resolution, variations of font type, size and color and oriented and multi-lingual text.

The textual information present in the text layer of borndigital images carries rich and precise high level semantics that would improve mining and retrieval of the web content, and would be useful in a variety of social and commercial applications. Most of prior methods for detecting or segmenting the text layer in scene or born-digital images have followed a bottom-up approach, by trying to find low level text components using local interest points (MSER), connected components or sliding windows [START_REF] Huang | Robust scene text detection with convolution neural network induced mser trees[END_REF], [START_REF] Jaderberg | Deep features for text spotting[END_REF]. The complex background, low resolution and the variability in text scale that characterize born-digital images, make such methods not very effective in localizing all the text. Additionally, after finding initial text interest candidates, some of them may be lost in the subsequent steps of classification and grouping.

Another technical challenge that faces text detection methods is: designing text features that would achieve high accuracy in text component classification. Many methods have followed the traditional approach of using hand-crafted features for training text classifiers [START_REF] Ye | Text detection and recognition in imagery: A survey[END_REF], [START_REF] Chen | Efficient text localization in born-digital images by local contrast-based segmentation[END_REF]. However, such features are usually database-dependent and their computation can be highly time-consuming. Hence, the more recent approaches in text detection (mostly in scene images) have turned to the approach of automatic learning of features via deep learning techniques. However, the problem of finding initial relevant and meaningful low-or high-level text components remains challenging, specially with multi-oriented and multi-scale text which appears in advertisements and other digitally-born images in the web.

In order to overcome all of the above mentioned challenges, researchers have -very recently -turned to holistic deep learning approaches, i.e. proposal-free text detection [START_REF] Tong He | Accurate text localization in natural image with cascaded convolutional text network[END_REF], [START_REF] Zhang | Multioriented text detection with fully convolutional networks[END_REF], [START_REF] Yao | Scene text detection via holistic, multi-channel prediction[END_REF]. The "proposals" refer to the initial text candidates or regions of interest before the learning and classification steps. In a proposal-free approach, the whole image as a pixel map is fed to a deep network, then after training, the network is able to output a corresponding heat map with classification labels of image pixels. This approach has been applied to scene text images and yielded superior performance compared to stateof-the-art methods.

In this work we have opted to follow the holistic (candidate-/ proposal-free) approach for detecting text regions in born-digital images. In particular, we use Fully Convolutional Networks (FCN) [START_REF] Shelhamer | Fully convolutional networks for semantic segmentation[END_REF] as a main component in our method. FCN have been developed and used very recently in computer vision for semantic segmentation, edge detection and a variety of problems, due to their holistic feature of taking full images as input.

Our method is composed of two modules: (1) The FCNbased module is trained in a holistic manner, and it generates semi-final candidate text regions through labeling text pixels, (2) The text layer formation module involves projection-based segmentation that splits the falsely connected text regions. The method is simple and generic, where the FCN module directly outputs highly accurate text regions at pixel level. Hence, our method works directly at pixel level of colored images, and gives each pixel a semantic label as text or non-text. This method has proven to be very effective for detecting text in both low-and high-resolution born-digital images.

The rest of this paper is structured as follows. Prior related work is reviewed in the next section, the description of the proposed method is detailed in Section III, and the experimental evaluation is presented in Section IV. The conclusions are discussed in the last section.

II. RELATED WORK

Text detection and segmentation in scene images and borndigital image have been hot research topics in the recent years, with the deep learning-based approaches becoming prominent in the last two years. An excellent comprehensive survey for this topic along with its scientific issues and challenges can be found in [START_REF] Ye | Text detection and recognition in imagery: A survey[END_REF]. This survey focuses on the classical approaches which are not based on deep learning. We note that much fewer works have focused on born-digital images [START_REF] Chen | Efficient text localization in born-digital images by local contrast-based segmentation[END_REF], [START_REF] Tehsin | Text localization and detection method for born-digital images[END_REF], [START_REF] Chen | Effective candidate component extraction for text localization in born-digital images by combining text contours and stroke interior regions[END_REF], [START_REF] Tehsin | A caption text detection method from images/videos for efficient indexing and retrieval of multimedia data[END_REF]. Those works -for born-digital images -all follow a traditional non deep learning-based approaches, and they rely on finding candidate (initial) components or interest regions as a first step.

The typical approach in deep learning-based methods is to find candidate (initial) components or interest regions, then classifying those candidates using convolutional neural networks (CNN) -based classifiers. Finding the initial candidates is done using MSER [START_REF] Huang | Robust scene text detection with convolution neural network induced mser trees[END_REF], CE-MSER [START_REF] He | Text-attentional convolutional neural network for scene text detection[END_REF], Sliding windows [START_REF] Jaderberg | Deep features for text spotting[END_REF] or Edge-boxes [START_REF] Jaderberg | Reading text in the wild with convolutional neural networks[END_REF]. This step can also be based on deep learning such as in the Region Proposal Network (RPN) [START_REF] Tian | Detecting Text in Natural Image with Connectionist Text Proposal Network[END_REF]. Then, the CNN-based classifiers assign the candidates text or non-text labels, character labels etc. After this stage, a refinement step takes place where words / text-lines are formed using one of various methods: grouping by visual and geometry features, context features, graph-based and also deep learning-based [START_REF] Zhang | Symmetry-based text line detection in natural scenes[END_REF].

In contrast to the typical approach, very few and very recent methods have followed a holistic approach so that to eliminate the need for finding initial text proposals. We review here those few methods as our method falls in this category. Zhang et al. [START_REF] Zhang | Multioriented text detection with fully convolutional networks[END_REF] have proposed a method for multi-oriented scene text detection using two FCN networks. The first FCN takes full input images and outputs pixel heat map with text classification probabilities. They train another FCN network to predict character centroids as a refinement step of the output of the first FCN. After that, they form text-lines using many steps which also handle finding text orientation.

He et al. [START_REF] Tong He | Accurate text localization in natural image with cascaded convolutional text network[END_REF] have presented Cascaded Convolutional Text Network (CCTN) for localizing text accurately in natural scene images. Their method is composed of two cascaded steps: (1): Coarse text region detection with a VGG-based network modified to handle multi-oriented and multi-scale text with parallel convolutional layers that have different kernels. This step is also holistic, it takes a full input image and outputs a pixel-level heat map. ( 2): Fine text-line detection with another VGG-based network: it takes as input the cropped rough regions which resulted from step (1), and outputs pixel maps. In the ground truth images, the central textline area of text bounding boxes is labeled as positive.

Yao et al. [START_REF] Yao | Scene text detection via holistic, multi-channel prediction[END_REF] have designed an interesting method called holistic, multi-channel prediction for scene text detection. Their work is based on a variant of FCN called the HED framework, where the input is a full image with a 3-side output layer: two pixel-wise prediction maps for text regions and individual characters regions, and a map of orientation values for linking between characters. The sub-networks are trained independently, then the outputs are fused together. These FCN-based methods have achieved the best of stateof-the-art results, specially regarding detecting oriented scene text. However, they all have a complex structure of more than one FCN network, and still face difficulties with the huge variability of text scale. The recent results show that the holistic approach is the most promising to follow and adapt for analyzing born-digital images.

III. THE HOLISTIC TEXT LAYER SEPARATION APPROACH

In this section, we present details of the proposed approach. In the training phase, colored images in their full size are fed as input to the main FCN module with their corresponding ground truth represented as binary label maps. We deal with detecting text regions as pixel-wise classification, and cast this classification as a binary semantic segmentation problem, where we have two classes with the labels: text or non-text at pixel-level.

The FCN-based network is built and trained to output the so called heat map (see Subsection III-A). This is a label image with confidence scores for each pixel being a text or non-text pixel. In the test phase, an image is fed to the trained FCNbased network, and we a get an output heat map. The second module performs connected component analysis on the output label map and uses projection profiles to split some of the resulting text regions into words and text-lines if needed. The final regions comprise the text layer of a particular test image.

Figure 1 shows a block diagram of the composing parts of our approach. The FCN-based module is trained in a holistic manner, and it generates semi-final candidate text regions through labeling text pixels. The text layer formation module involves projection-based segmentation that splits the falsely connected text regions. The method is simple and generic, where the FCN module directly outputs highly accurate text regions at pixel level. We will show how the FCN-based network is successfully trained and tested on multi-scale text. Additionally, this module could be trained on multi-oriented and multi-lingual text, because we pose no assumptions or preprocessing steps that are script dependent or orientation dependent. discriminate the large variety of text components from the complex background. Our FCN-based module learns both local and global text related features around a text pixel. Moreover, our approach does not require complicated preprocessing steps for preparing input images, but at the same time, it allows for any post-processing to be applied on the resulting generic text regions within the text layer. Any subsequent layout analysis steps could be performed on the detected text layer.

This holistic FCN-based training overcomes the limitations of the approaches which rely on character or other text component detection. Such approaches cannot robustly

A. The FCN-based Text Region Detection

Our FCN-based module is built by modifying and adapting the architecture of the fully convolutional models for semantic segmentation of natural objects proposed recently by Shelhamer et al. [START_REF] Shelhamer | Fully convolutional networks for semantic segmentation[END_REF]. The latter network was also built from the famous 16-layer VGGnet where the fully connected layers are converted to 1x1 convolutional layers to preserve spatial information.

The network design in our work is customized for text detection as shown in Figure 2 and as follows. The base net is similar to the FCN described in [START_REF] Shelhamer | Fully convolutional networks for semantic segmentation[END_REF] and is composed of 13 convolutional (CONV) layers, and each of them is followed by a RELU layer. The CONV layers are separated by 5 maxpooling (POOL) layers arranged as seen in Figure 2: 1 POOL layer after the first 2 CONV-RELU layers, 1 POOL layer after the second CONV-RELU layers, and then 1 POOL after each 3 consecutive CONV-RELU layers. The first CONV layer takes image data as input.

As seen in the design in Figure 2 After the base net comes the fully convolutional part of the network where 2 fully connected layers are converted to (replaced by) equivalent 2 fully convolutional layers. As known, the fully connected layers produce non-spatial outputs, but in FCN networks, the fully connected layers are handled as convolutions with kernels that cover their entire input regions. Hence, they become capable of taking an input image of any size and output per-pixel classification maps. Each of the two fully convolutional layers is followed by a RELU layer and a dropout layer for better learning generalization.

Another CONV layer takes its input from the last dropout layer and has 2 outputs that correspond to the number of classes (text versus non-text). The first output map is produced by a deconvolution layer (DeCONV) that follows the previous layer with a kernel size of 4 and a stride of 2. This produces an output of the size of the input image. The deconvolution here is in effect an upsampling process to get back the spatial pixel locations of the image. With the proper kernel and stride sizes, the CONV output is converted to a spatial map.

In this DeCONV layer, if we used the parameters (64, 64, 2)[32, 1], we could stop here and get the desired output. However, due to the large stride size of 32,w eg e t a coarse output (the resulting text region or text pixel classification output is not accurate enough). Hence, as designed in Shelhamer et al. [START_REF] Shelhamer | Fully convolutional networks for semantic segmentation[END_REF], we also use the outputs from previous layers to get a finer output as follows.

The output of the last POOL layer, is fed to a CONV layer, and then via a crop layer and a fusion function, the output of the CONV layer is fused with output of the DeCONV layer. The output map is obtained by a second DeCONV layer of a kernel size 32 and a stride 16 to recover the spatial predicted image. A crop layer is used to map the output of the convolutional layer to the input image data layer. Then the loss is computed by a Softmax layer which compares the ground truth label image to the segmentation output of the crop layer.

Overall, this design allows the network to handle variations in text scale, and in general the low resolution born-digital images. The final result of this part of our approach is a per-pixel heat-map that indicates the probability of each pixel being a text or non-text.

B. FCN-based Model Training

In the training phase, the FCN network described above is initialized as follows. The weights till the last Dropout layer are initially copied from the pre-trained model of VGG16 network as done in fine tuning training. The layers after that are all related to our text/non-text classification problem, so they are initialized with new weights by Xavier weights initialization. The training process is a supervised learning one, the loss layer takes the ground truth label images to compute the loss. The ground truth is prepared in two variants as follows. In the first variant: text pixels are labeled as positive (text class), the pixels inside the bounding box of text words are labeled as "ignored" and background pixels are labeled as negative (nontext class). In the second variant, both the text pixels and the pixels inside the bounding box of text words are labeled as positive (text class), and the rest is labeled as negative. Figure 3 shows example ground truth images of the two variants with their corresponding input images. In the second variant, a text region is considered as an object, which provides strong semantic information from the local context around the actual text pixels.

The solver parameters for carrying out the training and testing processes are detailed in Subsection IV-B. Additionally, we augmented the dataset to achieve a more robust training and prediction results. The network gives dense prediction based on the deconvolution (upsampling) and the pixel-wise loss.

In this way, our FCN-based network transforms the original image layer by layer from the original pixel values to the final class scores. The deep layers containing the learned feature maps carry knowledge about the text including low level properties and also about the local context of text components. The trained FCN is a strong text labeling model that does not make any assumptions about the orientation of the text or its script. This makes such a model applicable for analyzing any content of born-digital images.

C. Text Layer Formation

The output from the previous module of our method is a heat map that contains predicted pixel-wise text labels. The union of all those pixels comprises the text layer. The FCN network yields roughly accurate text regions that correspond to words or text lines of the input image. Even in the ground truth, the words may appear very close to each other within a textline due to the low resolution of a born-digital image.

Our goal is to separate and extract all the text in a text layer without necessarily segmenting the content into words. The complex layout of born-digital images does not allow for traditional layout analysis methods to find textlines. Once the text layer is segmented out, a post-processing method can be applied to achieve any desired level of text granularity.

In order to further enhance the text regions, we convert the heat map to a binary label image, and perform connected component analysis on it. The obtained components correspond to text regions at different granularity. For each component, we get the corresponding heat map region, and analyze its projection profile parallel to the largest principal axis. We split the region into two or more sub-regions at the low points (minima) of the projection profile. Figure 4 shows this steps of this process and the final text regions. The effect of this is getting more accurate text regions, for example splitting two attached lines or words into two separate lines or two words respectively. The union of those final regions forms the text layer of an image.

IV. EXPERIMENTAL EVALUATION

We have implemented our method in a text classification system, and evaluated this system on a standard public database for born-digital images. In the following subsections we detail the settings of our experiments and analyze the results.

A. Database and Evaluation Metrics

We evaluated the performance of our method on the IC-DAR 2013 Robust Reading Competition Challenge 1 on borndigital images [START_REF] Karatzas | Icdar 2013 robust reading competition[END_REF]. Images that were originally synthesized on computers such as advertisements and web images with embedded text are called born-digital images. Many content authors choose to embed text in images, rather than encoding it explicitly in the electronic document. This hinders the process of web information retrieval [START_REF] Karatzas | Icdar 2013 robust reading competition[END_REF].

The database contains 551 in total, and according to the competition settings, 410 images are assigned for training and 141 images for testing. The minimum resolution in this database is 100x100 pixels. Born-digital images are generally characterized by their low resolution such as the images embedded in webpages and email messages. However, some of them have high resolution such as advertisement images.

As for evaluation metrics, we use the standard recall, precision and f-measure metrics as done in most scene text detection works, and also in RRC competitions [START_REF] Karatzas | Icdar 2013 robust reading competition[END_REF]. In such evaluation, a text word (or bounding box) detection is considered as a correct detection if the overlap ratio between the detected box and the ground truth bounding box is ≥ 0.5.

B. Experimental Setup

The train/test split of the used database is as explained above (410/141 images). The FCN-based network solving parameters are as follows. The loss is averaged each 20 iterations, and learning rate is fixed during training where are base learning rate is 1e -10 . The FCN networks use a high momentum of 0.99. The iteration size is set to 1 so that to prevent gradient accumulation. The weight decay is set to 0.0005. Finally, the maximum training iterations is set to 100000.

For both the training and testing phases, the input images are fed to the network in their original variable resolutions. Interpolation surgery is applied on the upsampling (DeCONV) layers to yield heat maps that correspond to the image size. This is applied as explained in [START_REF] Shelhamer | Fully convolutional networks for semantic segmentation[END_REF].

C. Results and Analysis

Two experiments are carried out while varying how the area around text pixels is labeled. As we mentioned in Subsection III-B, two variants of the ground truth are prepared. The second labeling variant -where all pixels within the text bounding box are labeled as positive -gives better results because (1) the text and non-text classes will be more balanced due to the increase in positive samples, and (2) the pixels around the actual text pixels carry local contextual cues about the text, and it is hard to distinguish them from the actual text pixels.

The resulting text label map which contains semi-final text regions is fed to the post-processing module to output the final text regions which comprise the text layer. Example results are shown in Figure 5. The figure shows that the detected text regions are mostly accurate and correspond to words or textlines in the test images. The text varies in scale in the images, but our method is capable of detecting almost all the text pixels. Those final text regions are evaluated compared to the ground truth using the evaluation metrics mentioned in Subsection IV-A. Table I shows the results. As can be concluded, the method achieves high accuracy in text pixel classification despite the much larger number of pixels that belong to background. This is proven through the values of both recall and precision related to the number of correct detections of text boxes. [START_REF] Chen | Effective candidate component extraction for text localization in born-digital images by combining text contours and stroke interior regions[END_REF] 87.95% 91.14% 89.51% Pal-ICDAR15 [START_REF] Chen | Efficient text localization in born-digital images by local contrast-based segmentation[END_REF] 85.44% 93.91% 89.47% Sams [START_REF] Tehsin | A caption text detection method from images/videos for efficient indexing and retrieval of multimedia data[END_REF] 89.40% 88.83% 89.11% USTB-TexStar [START_REF] Yin | Robust text detection in natural scene images[END_REF] 82.38% 93.83% 87.74%

The highest achieved results in published state-of-the-art methods -for the task of text detection in born-digital images -i s89.51% using the standard f-measure according to Chen et al. [START_REF] Chen | Effective candidate component extraction for text localization in born-digital images by combining text contours and stroke interior regions[END_REF]. The latest results for the same task can also be found in works prior to Chen et al. in 2016 [START_REF] Chen | Effective candidate component extraction for text localization in born-digital images by combining text contours and stroke interior regions[END_REF], such as the other work of Chen et al. in 2015 [START_REF] Chen | Efficient text localization in born-digital images by local contrast-based segmentation[END_REF] and in the RRC2013 competition report [START_REF] Karatzas | Icdar 2013 robust reading competition[END_REF].

As can be seen in Table I, our method performs competitively to-or better than the best state-of-the-art methods in terms of the three evaluation metrics. In our method, we do not process the detected text lines to get words, whereas the evaluation is actually done at word level and so are the reported f-measure results of state-of-the-art methods. Hence, the evaluation tool penalizes the text box that contains more than one word. In some cases (as can be seen in Figure 5), our method yields such text boxes. This could be improved by applying a post-processing or grouping methods for splitting/merging the detected text boxes into words. We argue that this would achieve even better performance of our method.

V. C ONCLUSIONS AND FUTURE DIRECTIONS

This paper has presented a method for separating the text layer in born-digital images in a simple holistic approach. The text pixels classification is cast as a semantic segmentation problem and is carried out using an FCN-based network. The final text regions are formed by splitting the less dense regions in the projection profiles of text connected regions.

We have shown that the choice of FCN networks fits very well the problem of detecting text of variable resolution in born-digital images. This is due to that they take input images in their full size and work directly at pixel level of colored images. As opposed to previous approaches that apply CNN classifiers on candidate text regions, our method does not require complicated preprocessing steps, and is able to directly output accurate enough text regions.

In principle, this method can be generalized to multioriented and multi-lingual text by extending the training data and improving the training process. As a next step, we will work on detecting multi-oriented text by both improving the architectural design on the FCN network and applying postprocessing steps to compute the orientation of text regions. In another direction, we would like to investigate using bounding box regression as a post-processing step to output highly accurate text regions that can be directly used for text recognition.

Fig. 1 .

 1 Fig. 1. Block diagram of the proposed method. The FCN module outputs a heat map in which the red pixels correspond to the positive text class. The text layer formation module splits the falsely connected detected text regions. The "text layer" output shows its comprising text regions in white color. The bottom part shows the detected text layer on top of the input test image.

Fig. 2 .

 2 Fig. 2. The detailed architecture of the FCN-based network used in the first module of our proposed method. The architecture shows how to recover a pixel-wise prediction map that corresponds to the size of the input image through deconvolution layers. The parameters of CONV and DeCONV layers are shown as (kernel size, kernel size, num. outputs)[stride, padding]. The parameters of the POOL layers are shown as (kernel size, stride).

  , the network can handle any input image size of [widthxheightx3]. This input holds the raw pixel values of the image, in this case an image of width, height and three color channels R,G,B. The 3D mean is computed across the training images. The mean is subtracted from each image (training or test image) before it is fed to the network.

Fig. 3 .

 3 Fig. 3. Ground truth preparation. The first row shows the original images. The second row shows the pixel-level segmentation ground truth provided in the dataset. The third row shows the first variant of the ground truth preparation used in our method, where the pixels inside the green bounding boxes except text pixels are labeled as ignored. The fourth row shows the second variant where all the pixels inside the text bounding box is labeled as text.

Fig. 4 .

 4 Fig. 4. The text layer formation module of the proposed method. At the top left: the original input image. The heat map resulted from the FCN module is shown second. The connected components of the heat map are analyzed via the projection profiles shown in the right column. After splitting the components at split points, we get the final output of text regions in the left bottom image.

Fig. 5 .

 5 Fig. 5. Example text detection results of the proposed method. The images are 5 test images of different resolutions from the born-digital images dataset in [16]. The detection results are shown in green boxes. The green regions are in most of the cases accurate and cover words or textlines of the text.

TABLE I .

 I

	Method	Metric	Recall	Precision	F-measure
	Proposed		88.38%	91.87%	90.09%
	Pal-DAS16

TEXT DETECTION ACCURACIES OF THE PROPOSED METHOD COMPARED TO STATE-OF-THE-ART METHODS ON THE DATASET OF BORN-DIGITAL IMAGES IN

[START_REF] Karatzas | Icdar 2013 robust reading competition[END_REF]

.

VI. ACKNOWLEDGMENTS

This work is funded by the "Agence Nationale de la Recherche (ANR)" in France under the AUDINM project.


Laurent Davoust

Yves Fouillet

Yoshito Ishida

Drop stirring flow under EWOD and EHD actuation: a new step towards biological sample preparation

Keywords: Electrowetting, Electrohydrodynamics, Drop, Mixing

niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

Droplets as common carriers for bio-chemical agents have found growing impact in lab-on-a-chips devoted to bio-medical analysis. The basic operations addressed by a droplet-based lab-on-a-chip include generation, motion, coalescence and cutting. ElectroWetting On Dielectrics (EWOD) is a well-known physical mechanism capable of promoting all these digital operations [1,2,3]. This paper aims at investigating the abilities of EWOD to perform drop stirring as a new and useful operation.

Purification of biological samples proves to be a process to perform firstly in a digital lab on chip. EWOD could be thought of as the natural physics to use in order to get a fully integrated chain of digital micro-processes including typically centrifugation of a liquid sample. A centrifugation within a drop followed by EWOD-driven cutting could be a good way to purify a liquid sample and to extract target biochemical species. Recent experimental investigations have demonstrated that any EWOD-driven motion of a drop, even if submitted to circular trajectories, is never able to provide the centrifugation level required for purification purposes [4].

DROP MIXING AND EHD INTERPRETATION

Quite recently, we have produced a very efficient stirring (velocity~1m/s) within a 1mm-drop submitted to EWOD actuation but staying at rest over isolated electrodes. Different experimental configurations have been studied, especially those which are able to produce stable vortices. A pretty well organised flow is made evident making use of fluorescent DNA strands (figure 2) and hollow glass beads covering drop surface (figures 3, 4). Considering the frequency range of the applied AC voltage (1 KHz, 50V rms), electrohydrodynamics of Taylor-Melcher type (EHD, [5]) is found to be responsible for arising of vortices via the tangential component of the jump momentum balance across the drop surface. Considering the Ohmic current is much larger than the displacement current, the only non-vanishing electric charges accumulate to the drop surface provided that the dielectric permittivities of the involved fluids are different (water/air for instance) and that the electric field displays a component normal to the drop surface (Gauss' law, figure 1).

At points of the drop surface where a tangential electric component E is made available, the resulting azimuthal Coulombic stress is balanced by a viscous stress. In this way, vortices are pumped within the drop. Depending on the way the drop is located with respect to the underlying electrodes, the EHD-driven flow exhibits either two or four vortices (see focusing of bead tracers on the vortices centres where local pressure is the smallest, figures 3, 4). A modelling is put forward to predict the EHD-induced flow within a liquid spherical cap. Numerical calculations are performed considering the surface Coulombic stress behaves as a momentum source. The agreement with experimental results is fairly good if a specific constitutive law for the contact line dynamics is introduced [6]. Original geometries of electrodes are suggested in order to enhance drop centrifugation. Ann. Rev. Fluid Mech., 1, 111 (1969) [6] L. W. Schwartz & R. V. Roy, Theoretical and numerical results for spin coating of viscous liquids, Phys. Fluids, 16, 569 (2004)

REFERENCES:

Figure 1 :

 1 Figure 1: First configuration studied: one water drop staying over stripe electrodes.Side and top views.

Figure 2 :

 2 Figure 2: Vortical flow inside the deposited drop as made evident from solubilized labeled DNA strands (see top view in figure 1).

Figure 3 :

 3 Figure 3: Same vortices made evident from the focusing of hollow glass beads over the drop surface. The water drop is as large as the actuation area.

Figure 4 .

 4 Figure 4. Vortices as made evident from the focusing of hollow glass beads over the drop surface. The drop is smaller than the actuation area (see also attached configuration in figure 1).