Sagnik Sen

2-dipath and oriented L(2, 1)-labelings of some families of oriented planar graphs

Keywords: 2-dipath L(2, 1)-labeling, oriented L(2, 1)-labeling, girth, planar graph, cactus, Halin graph

In this paper, we improve the existing bounds [2] for 2-dipath and oriented L(2, 1) span for the class of planar graphs with girth 5, 11, 16, cactus, wheels and leaf independent Halin graphs. Some of these bounds are tight.

Introduction

In this paper, p and q are non-negative integers. A k-L(p, q)-labeling of a graph G is a function ℓ from the vertex set V (G) to the set {0, 1, ...., k} such that -| l(u)l(v) |≤ p if u and v are at distance 1 in G, -| l(u)l(v) |≤ q if u and v are at distance 2 in G.

To distinguish close and very close transmitters in a wireless communication system, Griggs and Yeh [START_REF] Griggs | Labelling graphs with a condition at distance 2[END_REF] proposed a variation of the Frequency Assignment Problem (or simply FAP) by introducing the above notion for the special case (p, q) = (2, 1) which was generalized by Georges and Mauro [START_REF] Georges | Generalized vertex labelings with a condition at distance two[END_REF] afterwards.

A common feature of graph theoretic models for FAP is that communication is assumed to be possible in both directions (duplex) between two radio transmitters and, therefore, these models are based on undirected graphs. But in reality, to model FAP on directed or oriented graphs could be interesting as pointed by Aardal et al [START_REF] Aardal | Models and solution techniques for frequency assignment problems[END_REF] in their survey.

An oriented graph is a directed graph with no cycle of size 1 or 2.

There are two different oriented versions of L(p, q)-labeling, namely, 2dipath L(p, q)-labeling, introduced by Chang et al [START_REF] Chang | Distance-two labelings of digraphs[END_REF], and oriented L(p, q)labeling, introduced by Gonçalves, Raspaud and Shalu [START_REF] Gonçalves | On Oriented Labelling Parameters[END_REF].

A 2-dipath k-L(p, q)-labeling of an oriented graph G is a function l from the vertex set V ( G) to the set {0, 1, ...., k} such that

-| l(u) -l(v) |≤ p if u and v are adjacent in G, -| l(u) -l(v) |≤ q if u and v are connected by a directed 2-path in G.
The 2-dipath span λ p,q ( G) of an oriented graph G is defined as max{k | G has a 2-dipath k-L(p, q)-labeling }. The 2-dipath span λ p,q (G) of an undirected graph G is defined as max{ λ p,q ( G) | G is an orientation of G}. The 2-dipath span λ p,q (F) of a family of (oriented or undirected) graphs is defined as max{ λ p,q (H) | H ∈ F}.

An oriented k-L(p, q)-labeling of an oriented graph G is a function l from the vertex set V ( G) to the set {0, 1, ...., k} such that l is a 2-dipath k-L(p, q)-labeling of G, -If xy and uv are two arcs in G then, l(x) = l(v) implies l(y) = l(u).

The oriented spans λ o p,q ( G), λ o p,q (G) and λ o p,q (F) are defined similarly as above.

The girth of a graph is the length of its shortest cycle. We denote by P g the family of planar graphs with girth at least g. A cactus is a connected graph in which any two cycles can have at most one vertex in common. We denote by C the family of all cacti.

A Halin graph is a planar graph constructed from a plane embedding of a tree with at least four vertices and with no vertices of degree 2, by connecting all the leaves with a cycle (called outercycle) that passes around the tree in the natural cyclic order defined by the embedding of the tree. An orientation H of a Halin graph H is said to be leaf independent if no two vertices on the outercycle are joined by a directed 2-path in the tree. Let H li denote the family of all oriented leaf independent Halin graphs. A wheel is a Halin graph whose tree is a star. Let W denote the family of all wheels.

Calamoneri and Sinaimeri [START_REF] Calamoneri | L(2, 1)-Labeling of Oriented Planar Graphs (Extended Abstract)[END_REF] studied 2-dipath L(2, 1)-labeling of some families of oriented planar graphs. In particular, they proved that λ 2,1 (P 11 ) ≤ 12, λ 2,1 (P 16 ) ≤ 8, 6 ≤ λ 2,1 (C) ≤ 8, and 8 ≤ λ 2,1 (W) ≤ 9. They also conjectured that λ 2,1 (P 5 ) ≤ 5.

In this paper, we disprove this conjecture, improve the above results and give some new results on 2-dipath and oriented L(2, 1)-labelings.

From the definitions, we have the following:

Lemma 1.1 For every (undirected or oriented graph) G and every p, q ≥ 0, λ p,q (G) ≤ λ o p,q (G).

A homomorphism f of an oriented graph G to an oriented graph H is a mapping f :

V ( G) -→ V ( H) such that xy ∈ A( G) implies f (x)f (y) ∈ V ( H).
Lemma 1.2 If there is a homomorphism f : G -→ H then λ p,q ( G) ≤ λ p,q ( H), for every p, q ≥ 0.

In this paper, we shall use the following from [START_REF] Hell | On nice graphs[END_REF]. A pattern Q of length k is a word Q = q 0 q 1 ...q k-1 with q i ∈ {+, -} for every i,

0 ≤ i ≤ k -1. A Q-walk in a digraph G is a walk P = x 0 x 1 .....x k such that for every i, 0 ≤ i ≤ k -1, x i x i+1 ∈ E( G) if q i = + and x i+1 x i ∈ E(G) otherwise. For X ⊆ V ( G) we denote by N Q (X)
the set of all vertices y such that there exists a Q-walk going from some vertex x ∈ X to y. We then say that a digraph G is k-nice if for every pattern Q of length k and for every vertex x ∈ V ( G) we have N Q ({x}) = V ( G). In other words, a digraph is k-nice if for all pairs of vertices x, y (allowing x = y) there is a k-walk from x to y for each of the 2 k possible oriented patterns. Observe that if a digraph G is k-nice for some k, then it is k ′ -nice for every k ′ ≥ k. Now we state a theorem from [START_REF] Hell | On nice graphs[END_REF].

Theorem 1.3 Let H k be a k-nice oriented graph, k ≥ 3. Every oriented graph whose underlying graph is in P 5k-4 admits a homomorphism to H k .

Subfamilies of Planar graphs

In this section, we state our results. Due to space limititions, almost all the proofs are omitted.

Theorem 2.1 λ 2,1 (P 5 ) ≥ 6.

To prove this theorem, we construct a planar graph of order 241 and girth 5 that does not admit any oriented 5 -L(2, 1)-labeling. This results disproves Calamoneri and Sinaimeri's conjecture. Theorem 2.2 λ 2,1 (P 11 ) ≤ λ o 2,1 (P 11 ) ≤ 10. To prove this theorem we construct a 3-nice graph that admits an oriented 10-L(2, 1)-labeling. The result then follows from Theoren 1.3, Lemma 1.2 and Lemma 1.1.

Theorem 2.3 λ 2,1 (P 16 ) ≤ λ o 2,1 (P 16 ) ≤ 7.
To prove this theorem we show that the graph B from Figure 1

Theorem 2.4 λ 2,1 (C) = λ o p,q (C) = 7. Proof (Sketch)
To prove this theorem, we first construct an example of a cactus C of order 600 with λ 2,1 ( C) ≥ 7.

We then prove that every oriented cactus admits a homomorphism to the oriented graph B from Figure 1. If not, let G be a minimal counterexample.

If there is a degree one vertex mal counterexample, there is a homomorphism

v in G such that v ∈ N + (u) (or v ∈ N -(u)) for some u ∈ V ( G), then G[V ( G) \ {v}] is also a cactus. As G is a mini-
f from G[V ( G \ {v}] to B.
Now, since all the vertices of B have at least one in-neighbour and one outneighbour, we can map v to any vertex

x ∈ N + (f (u)) (or x ∈ N -(f (u))).
If there is no degree one vertex in G then there is at least one cycle C ⊆ G such that exactly one vertex z of the cycle C has degree greater than 2 (since G cannot be a cycle). Now,

G[V ( G) \ {V ( C) \ {z}}] is a cactus and, since G is a minimal counterexample, there is a homomorphism f from G[V ( G) \ {V ( C) \ {z}}] to B.
Claim: Let O be an oriented cycle. Given any x ∈ V ( O) and y ∈ V ( B), there exists a homomorphism h : O -→ B such that h(x) = y.

If the claim is true then we can extend f to a homomorphism of G to B, which will end the proof.

Proof of the claim: We know that B is 4-nice. It is then enough to prove that for any oriented 3-cycle T and given any x ∈ V ( T ) and y ∈ V ( B), there exists a homomorphism h : O -→ B such that h(x) = y. In other words, we need to show that for each y ∈ V ( B), the 3-cycles in Figure 2 are subgraphs of B, which can easily be checked.

Clearly, λ o p,q (B) = 7. Then, we use Lemma 1.1 and Lemma 1.2 to conclude the proof. ✷ Theorem 2.5 λ 2,1 (W) = 8.

To prove this, we partition W in three different subfamilies and define for each of them a procedure to construct a 2-dipath 8-L(2, 1)-labeling of any graph in it. This will prove that λ 2,1 (W) ≤ 8. The lower bound was proved in [START_REF] Calamoneri | L(2, 1)-Labeling of Oriented Planar Graphs (Extended Abstract)[END_REF].

Theorem 2.6 7 ≤ λ 2,1 (H li ) ≤ 8. Proof (Sketch) For any G ∈ H li with outercycle O we give a 4-λ 2,1 -labeling f of O with | {v ∈ V ( O)|f (v) = 3} |≤ 2. Notice that T = G[V ( G) \ {x ∈ V ( O)|f (x) = 4}
] is a tree. We give a 2-dipath L(2, 1)-labeling f ′ of T using only labels from {4, 6, 8} such that f ′ and f restricted to {x ∈ V ( O)|f (x) = 4} together gives a 8λ 2,1 -labeling of G. This gives the upper bound. For the lower Fig. 3. The leaf independent Halin graph H li bound, we show that λ 2,1 ( H li ) = 7 ( H li is the graph in Figure 3). ✷

Conclusion

In this paper we consider the problem of determining λ 2,1 and λ o 2,1 of some families of planar graphs. In some cases, we provide improved bounds, some of them being tight. However, many problems remain open and there is room for improvements and many other interesting questions on this topic.

Fig. 1 .

 1 Fig. 1. B is a 4-nice graph.

  is 4-nice. Clearly, λ o 2,1 (B) = 7 and the result follows from Theorem 1.3, Lemma 1.2 and Lemma 1.1.

Fig. 2 .

 2 Fig. 2. Four different 3-cycles with respect to the vertex y.

This work is supported by ANR GRATEL project ANR-09-blan-0373-01

Email: sagnik.sen@labri.fr


Tien Sy Nguyen
email: tien-sy.nguyen@etu.univ-orleans.fr

Stephane Begot

Florent Duculty

Jean-Christophe Bardet

Manuel Avila

PAVEMENT CRACKING DETECTION USING AN ANISOTROPY MEASUREMENT

Keywords: crack detection, image analysis, road classification

Automatic pavement cracking detection is a part of road maintenance and rehabilitation strategies. Cracks detection is one of the main features used by road authorities to manage efficiently its networks. Different systems are available to perform road analysis. We give a short description of some of them. Apparatus which was used to provide our images is described with more details. Road surface is made using randomly organized aggregates which can have different sizes. Scanned pictures of theses surfaces appear as random distribution of a reduced set of gray levels. Automatic crack detection is a difficult task due to the noisy pavement surface. In this paper, we introduce a measure of anisotropy for the characterization of cracks. The basic idea of this method is to detect the variation of features by considering different orientations. Noise variation and defect properties can be take into account by our method. Comparative results of anisotropy method with threshold method and 2D wavelet transform method are presented to illustrate benefits of anisotropy. We show that this method can be used to detect others types of defects, such as joints.

Introduction

To efficiently manage the road network, road authorities need accurate and up-to-date information on the road condition. Defect information is vital to keep wellmaintained road networks. Nowadays, in France, thousands of kilometers of roads are inspected each year. Because huge amount of image data must be inspected, boringness of inspection task, and in addition easy-tomake-mistake task, the automatic pavement cracking detection is highly required [START_REF] Nguyen | Detection of Defects in Road Surface by a Vision System[END_REF]. There are several types of defects on road, some examples are shown in Figure 1. Cracks are the most frequent defect type. Road managers need to detect and to fix these defaults before they turn into serious problems such as pot-holes and pop-outs. Pavement cracking detection is not a "simple" edge detection problem or a texture analysis problem due to the nature of these images. Various pavement textures can be encountered on pavement surface images. Secondly, many road surfaces are "strong textures" [START_REF] Subirats | Automation of Pavement Surface Crack Detection using the Continuous Wavelet Transform[END_REF]. Cracks can be thinner than aggregate size and space between them. Distribution of aggregates in pavement is strongly random due to variation of their size and their random organization. There could be a lot of noise in the images. Light condition and surface of pavement can provide lot of variation. Consequently, it is hard to distinguish a crack with aggregate distribution. Find out "homogenous" features of road texture to detect pavement cracks is a very difficult task.

General approaches of defect detection in textured surfaces try to find a "homogeneous" feature of "defect-free" textures and compare the differences caused by defects presence [START_REF] Oliveira | Identifying and retrieving distress images from road pavement surveys[END_REF]. Several methods for defects detection in textured surface have been discussed in [START_REF] Kumar | Defect detection in textured materials using optimized filters[END_REF], but most of these methods are for defects detection on uniform or nearly uniform texture. In these studies, two important features were used. These features are orientation and pattern frequency. None of these methods have been successful in pavement crack detection. Most of existing methods of pavement crack detection are based on feature of crack, not on feature of "free defect" road surface. A scheme for crack detection method is usually divided in four steps: Pre-processing, Image Post-processing step is used to reduce noise and to connect small segments of cracks.

The last step, the cracks extraction is to find out presence of cracks and locate them on images.

Pre-processing Contrast stretching [START_REF] Nguyen | Detection of Defects in Road Surface by a Vision System[END_REF][START_REF] Chou | Pavement distress evaluation using fuzzy logic and moment invariants[END_REF] Equalization histogram [START_REF] Oliveira | Identifying and retrieving distress images from road pavement surveys[END_REF][START_REF] Cheng | Novel approach to pavement cracking detection based on fuzzy set theory[END_REF] Road image segmentation Fixed threshold [START_REF] Nguyen | Detection of Defects in Road Surface by a Vision System[END_REF][START_REF] Chua | Simple procedure for identifying pavement distresses from video images[END_REF][START_REF] Nallamothu | Experimenting with recognition accelerator for pavement distress identification[END_REF][START_REF] Kalikiri | Image-processing methods for automated distress evaluation[END_REF][START_REF] Tomita | Computer analysis of visual textures[END_REF] Fuzzy entropy threshold [START_REF] Cheng | Novel approach to pavement cracking detection based on fuzzy set theory[END_REF][START_REF] Chou | Pavement distress evaluation using fuzzy logic and moment invariants[END_REF] Wavelet transform and threshold on the space of coefficient [2,5] Post-processing Morphology operation [START_REF] Nguyen | Detection of Defects in Road Surface by a Vision System[END_REF][START_REF] Cheng | Novel approach to pavement cracking detection based on fuzzy set theory[END_REF][START_REF] Rasse | Application of image analysis to the identification and rating of road surface distress[END_REF] Connectivity Searching [START_REF] Cheng | Novel approach to pavement cracking detection based on fuzzy set theory[END_REF][START_REF] Meignen | Méthodes d'imagerie: Premiers résultats[END_REF][START_REF] Liu | Novel Approach to Pavement Cracking Automatic Detection Based on Segment Extending[END_REF][START_REF] Li | Novel Approach to Pavement Image Segmentation Based on Neighboring Difference Histogram Method[END_REF]

Crack extraction

Projection [START_REF] Nguyen | Detection of Defects in Road Surface by a Vision System[END_REF][START_REF] Subirats | Automation of Pavement Surface Crack Detection using the Continuous Wavelet Transform[END_REF][START_REF] Cheng | Novel approach to pavement cracking detection based on fuzzy set theory[END_REF][START_REF] Delagnes | Extraction d'inhomogénéités dans les images texturées fixes et animées[END_REF] Hough transform [START_REF] Subirats | Automation of Pavement Surface Crack Detection using the Continuous Wavelet Transform[END_REF][START_REF] Cheng | Novel approach to pavement cracking detection based on fuzzy set theory[END_REF] Neural Networks [2, 13] Table 1: Summary of methods for crack detection on road surface images.

Most of these existing methods, only use local feature of crack to segment images. Crack pixels are considered as darker pixels or as local extrema, but connectivity and orientation of crack were not considered in the segmentation process. In fact, due to nature of road textures, many crack-free pixels have a grey level as low as crack pixel. Consequently, result of segmentation could contain noises (example in Figure 2). Geometrical characteristics of cracks have been taken into account in the post-processing step to reduce noise and to connect crack pixels. But this task of discrimination between the noisy pixels and crack pixels is not an easy task. In [START_REF] Oliveira | Identifying and retrieving distress images from road pavement surveys[END_REF], Oliveira & al use a Bayesian classifier applied on small windows of the image. Features used are mean and standard deviation of pixel intensities. Sample images, shown, seem to be captured in optimal condition. There is a few variation of pixel intensities. It is not true in case of dynamic acquisition with a line scan camera on high performance apparatus [START_REF]Vectra's AMAC® specifications[END_REF].

Outline on actual system for road crack inspection

On-road visual defect detection

First methods of road crack detection are on-road visual detection. Technicians travel in a vehicle at speed of 5 to 10 kilometers per hour. Driver watches the road and when a crack is found, passenger records the cracks onto a dedicated board acquisition device. This method is slow and unsafe not only for road monitoring staff but also for road users.

To overcome limitations of visual inspection, the idea is:

Whether "to bring road to office"-Road images are firstly captured by a high speed acquisition device, and then, the inspection process is done offline by inspectors viewing captured images. Or, the device must be able to detect automatically road defects in real time and at high speed. Some such devices are CSIRO's RoadCrack vehicle [START_REF]RoadCrack Specifications[END_REF], Roadware's ARAN system [START_REF]Wisecrax data sheet[END_REF]. Unfortunately, because of the commercial nature of these systems, hardware and software used have not been published. Besides, by difference of road pavement texture, tests made in French road network show that both of ARAN and RoadCrack systems do not satisfy the requirements for French road maintenance. Road maintenance in France requires information about cracks as small as 1 mm wide. Because huge amount of image data must be inspected, the boringness of inspection task, and in addition, the easy-to-make-mistake task, automatic or semi-automatic detection of cracks on road images is highly required.

AMAC® System for Road Analysis in France

Conditional Texture Anisotropy

Crack characteristics

By deduction from other types of work on pavement crack detection, and from our crack analysis, three important crack characteristics can be singled out:

Local extremum due to illumination model (Figure 4), Continuity: Width of crack may be smaller than aggregates and also smaller than the distance between them but length of crack is always longer than aggregates, Dominant orientation: Analysis of image database shows that cracks have dominant directions (longitudinal, transversal). In case of alligator cracks, direction is dominant in each segment.

Definition of Conditional Texture Anisotropy

Now, we introduce an algorithm to segment crack images. This method take into account the three characteristics (3.1): gray intensities, connectivity and orientation of cracks during segmentation step. Conditional Texture Anisotropy (CTA) was introduced by F. Roli in [START_REF] Roli | Measure of texture anisotropy for crack detection on textured surfaces[END_REF] The main idea is to find out a measure which has a different value in one direction (along the orientation of crack) between other directions. In [START_REF] Roli | Measure of texture anisotropy for crack detection on textured surfaces[END_REF], CTA was defined as:

{ } { } { } 1 1 1 m a x ( / ) m i n ( / ) ( ) max ( / ) l l j j j j l l j j p x l w p x l w CTA X p x l w ∈ - ∈ = ∈ (1)
With vector ( )

l m l l l x x x X ,... , 2 1 = composed of sub-vector ( ) l j l j l j l j k feature feature feature x _ ,... 2 _ , 1 _ =
representing k different features of l pixel along different j orientations (e.g. 0°,45°, 90° and 135°). According to pattern recognition theory, function 1 ( / ) l j p x l w ∈ (w 1 being the class of defect-free pixels) can be computed with parametric or non parametric techniques [START_REF] Tomita | Computer analysis of visual textures[END_REF].

As described in [START_REF] Roli | Measure of texture anisotropy for crack detection on textured surfaces[END_REF], CTA takes values close to 0 for freedefect region. In this case, feature values extracted according to each orientation are close together. Around defects, CTA will take values close to 1. For example, along crack orientation, feature values will be very different from others directions. This measure is said to be 'conditional' because it takes into account the kind of texture.

In [START_REF]RoadCrack Specifications[END_REF], F. Roli gives a CTA example for crack detection on granite slab images affected by crack. Four texture features were computed using the Fourier power spectrum. Nonetheless, the formula for calculating CTA was not explained.

Crack detection on road surface by CTA

According to cracks characteristics on road surface images, we have chosen mean and standard deviation as two features for calculating CTA. The method of calculation is presented as follows: 2*d+1 is the length of a line, along which we calculate each feature. d should be chosen as 2*d+1 >> aggregate size to satisfy assumptions made in part 3.1. Four directions 0°, 45°, 90° and 135° are considered. mean l j m and standard deviation l j σ , of 2*d+1 pixels along considered direction j, are calculated. Feature vector of pixel l along j orientation is ( , )

l l l j j j x m σ = (2)
To evaluate the pre-assumed probability 1 ( / )

l j p x l w ∈ of a
pixel l to be "a defect-free pixel according to orientation j", we calculate :

( ) D D w l x p j l j Δ - = ∈ 1 / (3) with 2 2 D m σ = + and ( ) ( ) 2 2 l j l j j m m σ σ - + - = Δ
m and σ are calculated on whole the image. These formula can be compared to a normalized distance which is close to 1 for defect-free pixel. Mean and standard deviation according to all directions are near "global" values. In case of crack pixel, distance j Δ along the orientation of crack is higher and value decrease towards zero. CTA is then calculated as in equation [START_REF] Nguyen | Detection of Defects in Road Surface by a Vision System[END_REF]. Remember that this is a pre-assumed probability value used for calculating CTA. We do not detect the crack by using this probability but by calculating CTA. The information which plays the most important role for crack detection is the distribution of mean and standard deviation values according to all orientations. zoom original image The distribution of CTA on a road surface image was supposed to be a Gaussian distribution (this hypothesis was verified in our experiment of road image analysis).

After calculating all values of CTA in an inspected image, for each inspected pixel l, the Mahalanobis distance is computed as: We see comparative results of our method with threshold method [START_REF] Nguyen | Detection of Defects in Road Surface by a Vision System[END_REF] and Subirat's method [START_REF] Subirats | Automation of Pavement Surface Crack Detection using the Continuous Wavelet Transform[END_REF]. The 2D wavelet transform raises the crack but it increases also noises because continuity was not considered (Figure 7 (b)). In the other hand, our method only raises the continuous crack pixels. The threshold method (Figure 7 (c)) has limitations because it cannot differentiate a dark pixel of defect-free texture from a crack pixel.

In our database, images should contain more than one kind of defect (joint, crack, pothole, …). In this paper, we only test crack detection, so we have chosen images containing only cracks. Table 2. shows results of our method tested on about 540 images, 235 crack images and 307 defect-free images. These images were selected randomly from our image databases which were already labeled by operators. Our experiments show that this method provides a very good detection of longitudinal and transversal cracks. Our method can detect cracks as small as 2mm (1mm=1 pixel), even the "well" continuous cracks as small as 1mm can be detected (Figure 6 (a)). Annexes, show some results. Limit of method are shown for cracks too thin and not oriented in one of the selected direction. Our method is disturbed by presence of spots in the texture, dark or white. We need to append at this detection some high level analysis to qualify spots detected.

In Figure 8, we show a detection result on defect image of joint type. Our method can detect this defect type with "high" value of d length ( in this example, d = 28).

Conclusion

In this paper, we introduced a method for crack detection on road surface images. A measure of Conditional Texture Anisotropy (CTA) is used to characterize pixels on inspected images. Each pixel is segmented into "crack pixel class" or "crack-free pixel class" based on the CTA value.

Unlike other methods that only considered defect pixel as a local minimum in their segmentation step, our method transforms pixel from image space to CTA space using different parameters of features: extremum, continuity, homogeneity and dominant orientation. Four traditional orientations (0°, 45°, 90° and 135°) were used to calculate CTA in our first implementation, because of the rapidity in finding neighbor pixels without doing any interpolation (0°, 45°, 90° and 135° correspond to 4 directions in 8-connex grid). By this way, the method produces good results on cracks detection having these orientations (transversal crack, longitudinal crack). We compare results with other methods in literature (threshold, wavelet transforms) and we show the efficiency of our method. We are prospecting to improve pertinence of our distance to assess the probability of pixel to be of free defect type. Some new features should be added. We are adjusting a fuzzy approach which seems to perform good results. To avoid limitation of the "arbitrary" orientations used, we are developing a more generic algorithm. All these evolution should be included in a global system which use high level knowledge of road defects.

Fig. 1 .

 1 Fig. 1. Some examples of road defects: longitudinal crack (a), transversal crack (b), alligator crack (c).

Fig. 2 .

 2 Fig. 2. Road crack detection by Subirat[START_REF] Subirats | Automation of Pavement Surface Crack Detection using the Continuous Wavelet Transform[END_REF]: inspected image (a), crack candidate pixel (b), result after post-processing (c).

Figure 3 .

 3 Figure 3. AMAC® apparatus for road analysis (a), image acquisition system used on AMAC® (b)

Fig. 4 .

 4 Fig. 4. Analysis of a crack, 3D profile (a), illumination model on a crack (b), continuity on a given orientation (c).

Fig. 5 .

 5 Fig. 5. Example of CTA for p 1 pixel, d = 10. Distribution of m and σ calculated on p 1 and p 2 along 4 orientations.

Figure 5

 5 Figure 5 illustrates a calculation sample of CTA on these two pixels, P 1 (a crack pixel) and P 2 (a free defect pixel). Values of mean and standard deviation ( , ) l l j j m σ along 4 orientations are: (99.1, 47.5), (93.7, 34.5), (37.9, 14.3) and (104.7, 39.4). With (123.5, 48.1) global values, value of CTA of P 1 is 0.64. With pixel P 2 , values of ( , ) l l j j m σ along 4 orientations are : (111.9, 36.0), (108.9, 25.8), (110.5, 33.4), (116.0, 29.6). The value of CTA of P 2 is 0,08.

  variance of CTA distribution of inspected image. As we see in figure 6 (b) and (e), values of crack pixel with Mahalanobis distance images are very high and contrast with others free defect pixels of images. Crack pixels are easily detected (Figure 6 (c), (f)) by a threshold from these distance images.

Fig. 6 .

 6 Fig. 6. Example of detection results. original images (a, d), Mahalanobis distance results (b, e). crack detection results (c, f).

Fig. 7 .

 7 Fig. 7. Anisotropy vs. Subirat's 2D wavelet transform method: inspected image (a), Subirat's method (b), threshold method (c), our CTA method (d).

Fig. 8 .

 8 Fig. 8. Result of our method on image with joint type defect. Image (a), zoom (b), mahalanobis distance image (c), crack detection (d)

Table 2 :

 2 Results of our method on real road images

Some fault detection

Image without defect : some defects detected

Some defect not detected

Image with defect : no detection


Vandoeuvre-lès-Nancy, France lieber@loria.fr, napoli@loria.fr

There is a long history of applications of decision support systems to oncology. Almost from the birth of the so-called "expert systems", programs dedicated to helping practitioners in establishing diagnostic, treatment or monitoring of cancers have been developed. Among the first to explore this area was ONCOCIN [START_REF] Shortliffe | Proc. of the 20th Computer Science Symposium[END_REF] in the mid 80's. Like many other systems, ONCOCIN was based on a set of rules, encoding the actions to trigger in specific situations. More generally, a clinical decision support system such as ONCOCIN is a computer program that takes as input the description of a medical situation, and provides as a result information supporting the practitioner in making the appropriate decisions concerning this situation [START_REF] Musen | Modeling for Decision Support[END_REF]. Such a program intends to capture, to encode, medical knowledge and to apply problem-solving method to automatically "reason" upon this knowledge.

While there have been a lot of research, prototypes and experiments on applying decision support systems in medicine and specifically in oncology, they have never been really adopted to support the daily practice of oncology. Expert systems, after having generating so much enthusiasm, have appeared disappointing and acquired a bad reputation. They where blamed not to be adaptive enough to particular situations, not to be helpful enough as they were not able to explain their results, and also not to be dynamic enough as they were hard to evolve together with the advances in medicine. However, the underlying technologies for decision support systems have evolved a lot since the early expert systems. Research in knowledge management has produced adequate methods for handling the difficulty of capturing and maintaining computerized expertise, and to provide the appropriate level of interaction between the system and the practitioner. Therefore, this might be the time to consider once again the question of decision support systems in oncology: Is their bad reputation still justified and what are the obstacles to their widespread adoption?

To derive elements of answer to these questions, we consider our concrete experience in building a modern decision support system in oncology: the Kasimir project.

The Kasimir project was born in 1997. It gathered specialists in oncology and researchers in psycho-ergonomics and in computer science. Its goal is decision knowledge management in oncology in the framework of Lorraine (a region of East of France). Such knowledge can be found in decision protocols, that are documents explaining the standard decision to be applied to some decision problems (standard, according to the medical state of the art, following the principle of evidence-based medicine). For example, the breast cancer treatment protocol describes the standard treatments, function of the description of a patient ill with breast cancer and of its cancer. Other decision protocols were considered in this project, e.g., prostate decision protocol, breast cancer surveillance, inclusion of patients in clinical trials, etc.

Two types of decision support have been studied in the Kasimir project: protocol application and protocol adaptation. The study of protocol application has led to computer programs within the Kasimir system that are nowadays stable and are based on standard methods and tools of the domain of knowledge-based systems (which is a subfield of computer science). Such a program has a friendly user-interface for describing a patient and its cancer and for displaying the associated standard decision [START_REF] Aquin | Knowledge Edition and Maintenance Tools for a Semantic Portal in Oncology[END_REF]. Some studies carried on by physicians have shown a statistically significant improvement of the observance of a decision protocol when the physicians use the Kasimir system, compared to their observance when they use the decision protocol in the form of a paper document [START_REF] Rios | Référentiels de bonnes pratiques cancérologiques : étude comparative de trois supports d'aide à la proposition thérapeutique pour les cancers du sein et de la prostate en Lorraine (Clinical guidelines in oncology: comparative study of three decision support systems for breast and prostate cancer in Lorraine French region)[END_REF].

For a majority of patients, the standard decision given by protocol application can be applied as such. The specialists in psycho-ergonomics involved in the project have shown that for the other patients (one third? 40%?), the oncologists adapt the decision protocol, i.e., actually use it, but with a critical eye and not in a straightforward way. There are many reasons why a protocol has to be adapted, e.g., drug contraindications, closeness to a decision threshold, psychological problems of the patient, cancer of a pregnant woman, breast cancer of a man, etc. The complex and rich domain of decision protocol adaptation has been deeply studied in the Kasimir project [START_REF] Lieber | Modeling adaptation of breast cancer treatment decision protocols in the Kasimir project[END_REF]) but still requires some research and development in order to obtain tools that could be used with benefit by physicians in their daily practice. Therefore, we have concentrated our effort for transfering this research to the medical community mainly on protocol application.

The key issue for having a tool for protocol application is the implementation of a computerized protocol, i.e., the translation of the decision protocol document into a machineunderstandable file expressed in a standard knowledge representation formalism. The translation process is not straightforward: it requires from the knowledge engineer in charge of this task to interact with physicians, in particular to better understand the medical notions used in the protocol and to point out some implicit pieces of knowledge (that are to be made explicit for computers). It also requires to be tested by an oncology specialist before being given to any physician. This entails some effort of oncology experts and of knowledge engineers for the first version of the computerized protocol as well as maintenance efforts for its next versions (in particular, a new version of the breast cancer treatment protocol is published every 6 months).

The end-users of the Kasimir system are physicians that are not highly specialized in oncology. The end-users we have met have tested the system for several weeks, and are willing to use it in their daily practice, which involves up-to-date computerized protocols. However, as mentioned above, this implementation of protocols and their maintenance require time of oncology experts. Unfortunately, because of the low demography of these specialists, at least in Western Europe, and because of the growing number of cancers, the time that the specialists can spend on tasks that are not in the center of their medical activity is getting lower and lower. Moreover, their benefit from this work is not obvious: as specialists in oncology, they do not need the help of such a decision support system.

Now, what is the future of the Kasimir system? At first glance, it seems that it is confronted to the so-called knowledge acquisition and maintenance bottleneck. Now, it can be remarked that oncology experts do spend a lot of time for acquisition and maintenance of decision protocols in the form of paper documents. Once these documents are published, it is understandable that the experts are reluctant to do an additional effort for validating the computerized protocol implemented by knowledge engineers. But must this effort be additional? The job of knowledge engineers is the management of knowledge acquisition and maintenance. Thus, would it be possible to settle an efficient synergy between oncology specialists and knowledge engineers that would lead to protocol in two forms (paper documents and computerized forms)? From our experience in the Kasimir project, our opinion is that such a synergy is possible and that it should lead to:

• A benefit in time for the oncology specialists (for the acquisition and the maintenance of the protocols and because simple cases-that do not require adaptation-can be managed by less specialized physicians); • A benefit in competence to less specialized physicians (able to solve at least simple cases); • A benefit in healthcare quality for the patients (having the level of speciality in oncology fitting the complexity of her/his case).

Such a shift in organization requires a political decision and an acceptance from the medical community. Our message from a computer science viewpoint is that this shift is technologically possible and should be beneficial.


Bart Lamiroy
email: bart.lamiroy@loria.fr

Daniel Lopresti
email: lopresti@cse.lehigh.edu

An Open Architecture for End-to-End Document Analysis Benchmarking

Keywords: benchmark, web services, document analysis, performance evaluation

In this paper, we present a fully operational, scalable and open architecture allowing end-to-end document analysis benchmarking without needing to develop the whole pipeline. By decomposing the analysis process into coarsegrained tasks, and by building upon community provided stateof-the art algorithms, our architecture allows any combination of elementary document analysis algorithms, regardless their running system environment, programming language or data structures. Its flexible structure makes it straightforward to plug in new algorithms, compare them to other algorithms, and observe the effects on end-to-end tasks without need to install, compile or otherwise interact with any other software than one's own.

I. INTRODUCTION

The issue of benchmarking, and more generally speaking, comparing results in experimental science, is a recurring and fundamental discussion (cf. [START_REF] Kanungo | Special issue on "performance evaluation: Theory, practice, and impact[END_REF], [START_REF] Nagy | Document systems analysis: Testing, testing, testing[END_REF], [START_REF] Valveny | A general framework for the evaluation of symbol recognition methods[END_REF] for an incomplete list in the document analysis domain). To compare reported results with others in an irrefutably objective framework is essential in all scientific domains. Better still is to be able to reproduce reported experiments and compare the obtained results with those published. Moreover, it is not sufficient to only have access to the outcomes of experiments; in many cases sound scientific debate arises over conclusions and deductions taken from a set of experiments when contesting parties question the validity of the claims on grounds of incomplete parameter scopes or experimental conditions. This is not only part of normal scientific experimentation, it is the core essence of scientific activity.

In the domains of machine perception, and document analysis in particular, many initiatives and efforts have emerged over the years, to provide the research community with tools that would allow sound contradictory debate and objective comparison between published methods.

They can be placed into several categories:

• annotated datasets, allowing experiments on the same data, and thus partially share parameters [START_REF] Phillips | CD-ROM document database standard[END_REF], [START_REF] Thoma | Automating the production of bibliographic records for MEDLINE[END_REF], [START_REF] Agam | The Complex Document Image Processing (CDIP) test collection[END_REF]; • execution frameworks and software, which allow experiments to run on shared code bases, and therefore have a greater level of interaction and re-usability [START_REF] Breuel | The ocropus open source ocr system[END_REF], [START_REF] Rendek | The search for genericity in graphics recognition applications: Design issues of the qgar software system[END_REF], [START_REF] Jaeger | DOCLIB: a Software Library for Document Processing[END_REF] (re-usability can be seen as some form of reproducibility); • data markup languages, while sometimes much related to the previous point, they allow for more transparent data sharing and comparison of experimental results [START_REF] Doermann | GEDI -A Groundtruthing Environment for Document Images[END_REF]; • contests, held at international conferences or hosted on a more continuous basis by scientific associations.

Despite these efforts1 , and despite the peer review processing, there still remains room for progress in the area of contradictory debate and objective comparison between published methods [START_REF] Lopresti | Document Analysis Research in the Year 2021[END_REF]. There are several factors that contribute to this, especially when it comes to reproducibility and comparison of results.

Shared datasets, for instance, while having significantly contributed to improving performance metrics [START_REF] Nagy | Document systems analysis: Testing, testing, testing[END_REF], fail in other cases to contribute to a productive debate. After being used for some time, research teams inevitably, and often unconsciously, learn to adapt to their specificities and implicit context assumptions; their "ground-truths" (or prerecorded interpretations) suppose a one-size-fits-all approach across all evaluations.

Execution frameworks and open-source software have the advantage of allowing users to share the same code base and experimental run-time conditions or input-output conventions. While this has a positive impact on reproducibility, their scope is sometimes limited, since users are coerced into software environments, programming languages or other operational constraints that may not be optimal in their specific context. Furthermore, these tools require significant efforts to maintain (open-source community development efforts require a critical mass to be self-sustaining) and may, over time, suffer from technological obsolescence, making them harder to maintain on newer platforms.

Contests are great tools for providing instant snapshots of the state of the art in the evaluation context that was specifically defined for the contest. Rarely do they offer the opportunity to "replay" the contest with other parameters, or even to compare contestants of one year with those of previous editions ... or to imagine what if scenarios where the evaluation or execution context are shifted into a different setting. The result is that their outcomes are static, and hence cannot support a dynamic debate.

Creating the ideal conditions for productive, reproducible experimental science is not an obvious task, and is certainly not one that can be achieved by anything short of a whole community. It cannot be dictated, but rather comes from a common adoption of what are considered best practices. The previously enumerated examples are steps in that direction. We believe that they can be re-formulated into a new paradigm, providing an even higher level of scientific trustworthiness in and reproducibility of reported experimental results [START_REF] Lopresti | Document Analysis Research in the Year 2021[END_REF]. Because of space constraints, we are only addressing those parts of the technical implications of this paradigm that are concerned with execution and reproduction of algorithms. Other aspects, focusing on data or interpretation storage and retrieval, result certification or provenance recording have been described before [START_REF] Lamiroy | A platform for storing, visualizing, and interpreting collections of noisy documents[END_REF], [START_REF] Lamiroy | How carefully designed open resource sharing can help and expand document analysis research[END_REF].

This paper will focus of the question of reproducibility from an operational point of view, and especially in the light of document analysis problems. It should be noted that the basic ideas we are presenting are more general and not confined to the field of document analysis.

We begin by analyzing in Section II the technical features required for a generic framework for supporting reproducible experiments. In Section III, we lay out the technologies and architectures that address these requirements and present the tools we have developed to implement our system.

II. REQUIREMENTS FOR REPRODUCIBLE SCIENTIFIC EXPERIMENTS

The question on how to produce and report scientifically sound and valid experiments is not new [START_REF] Popper | The Logic of Scientific Discovery[END_REF], it is an ongoing debate in all disciplines, e.g. [START_REF] Moret | Algorithms and experiments: The new (and old) methodology[END_REF], [START_REF] Schwab | Making scientific computations reproducible[END_REF].

The basics are: 1) reporting of clearly set goals and defined interpretation framework, 2) full access to all experimental data, 3) reporting of the experimental apparatus, setup and protocol, in such a way that it becomes fully reproducible, 4) all parameters defining the data (if applicable) and those related to the experimental process. While these seem obvious, and are apparently met by the initiatives presented previously, the currently available resources fail to produce the effect of fully reproducible open experiment reporting. The reasons for this include:

Full disclosure and complete reporting: is often difficult to achieve for methods and algorithms, notably because of space constraints on publications. Even if the reporting is completely transparent, it still may be hard to reproduce complex algorithms and obtain identical behavior due to implementation choices, bugs, etc. Making source code available, or using shared development or execution platforms [START_REF] Breuel | The ocropus open source ocr system[END_REF], [START_REF] Rendek | The search for genericity in graphics recognition applications: Design issues of the qgar software system[END_REF], [START_REF] Jaeger | DOCLIB: a Software Library for Document Processing[END_REF] is helpful, but practice shows that this only rarely yields comparative studies. The reason for that is that the platforms are very much technology dependent (choice of specific programming languages, operating systems, data structures or other constraining paradigms) that often require a time investment that discourages others from using it. They also may suffer from progressive obsolescence when not actively maintained. Releasing source code can also be problematic when private funding, IP or patents come into play.

Full access to all experimental data: should not really be an issue, given today's ubiquitous access to storage and bandwidth (although this does become an issue when the amount of data becomes too large [START_REF] Smeaton | Evaluation campaigns and TRECVid[END_REF]), but there are more subtle difficulties. The way benchmark datasets are currently conceived and made available is rather "monolithic" in the sense that they have usually been created for a specific experimental context, and that their intrinsic parameters (e.g. type of images, resolution, content, frequency ...) and associated interpretations are those that suit this context. In order to adapt to these implicit constraints, re-use of existing datasets often comes with recomposition, selection and filtering of the original data, blurring the exact boundaries of the effectively used data.

Exact description of all parameters: is difficult to provide, especially for data, since they often reflect a mix of arbitrary design decisions (my method does only take .tif images) and more subjective ones ("reasonably" good scan quality so that the OCR doesn't fail). Because of different experimental contexts, it is rarely the case that exhaustive experiments are reported over complete datasets, without the selection and filtering mentioned beforehand. This also sometimes holds for contests where training data is not always formally characterized, for instance.

The result is that most of the time, results are reported and published in good faith and that peer reviewers need to find the subtle compromise between investigating the veracity of the alleged claims and their experience-backed feeling of their plausibility. This also holds for readers who would want to build upon published results, either to compare their own methods to the published ones using the same experimental context, or to change the experimental context and setup to test the published approaches with other data.

In order to achieve the goals described in this section, any published result (data, algorithm and experimental setup parameters) should be transposable in any context and should allow any user, using any kind of environment to immediately reproduce the experiments in the exact same conditions as reported. Elsewhere we have addressed some of the issues in referencing datasets and interpretations [START_REF] Lamiroy | A platform for storing, visualizing, and interpreting collections of noisy documents[END_REF], [START_REF] Lamiroy | How carefully designed open resource sharing can help and expand document analysis research[END_REF]. The following sections will focus on how to reproduce experimental setups and run algorithms in the exact same conditions as published.

III. GLOBAL ARCHITECTURE

The solution presented here has been tested and integrated in the DAE platform at http://dae.cse.lehigh.edu/DAE. Its global architecture is represented in Fig. 1. It is noteworthy to mention that the platform itself is merely a validation of the concepts presented in this paper, and that the latter can be implemented outside of the platform without loss of the general goals announced in the previous section.

A. Document Analysis Algorithms as Web-Services

Rather than to require user to adopt a specific programming paradigm, dedicated libraries or integrated systems, we propose to build our solution on an open standard and to publish algorithms as web services [START_REF] Booth | Web services description language (WSDL) version 2.0 part 0: Primer[END_REF]. This solution offers the following advantages:

Platform Independent Open Standard: web services are built upon a series of standards that are well documented and widespread. They can be accessed and used through a great variety programming languages and execution environments. While platform independent, they are completely interoperable, and services running in one environment/language can exchange data and collaborate seamlessly with services running elsewhere.

This means that this approach is not incompabible with conventions users may have to run their experiments in their preferred environment, while, at the same time, giving them access to software and experiments of others.

Formalized I/O: WSDL is part of the previously mentioned standard. It permits formalizing the input and output of services in a detailed way, and to provide service brokers to publish the list and location of available services. These are important features from a functional point of view, since they improve the level of re-usability and interaction with provided services. It makes it, for instance, possible to have more "semantic" information on the required inputs and provided outputs of an algorithm implementation and use zero-programming environments. These environments provide the opportunity to combine and connect available services into complex workflows, and "program" end-to-end pipelines (in our case document analysis pipelines) made out of multiple external individual programs (cf. Taverna, discussed in Section III-C).

No Code Re-Engineering: because of the open standards and the formalized I/O, there is no real need to reengineer existing code to make it available as a web service nor is there any need to do so to adapt and re-use an existing service in one's personal environment.

Although the above statement is true, existing software doesn not turn into a web service by itself. There are multiple degrees of integration with the web service paradigm that can be envisaged and engineered. At the lowest level, providing the existing code does not require interactive user input and runs as a standalone command-line program, it is possible to use off-the-shelf wrappers that call the code as an external command (e.g. those provided in Section III-B).

Smooth Learning Curve (if any): given the facts enumerated above, the whole framework presented in this paper is totally non-disruptive with users' usual way of working and experimenting. They continue to develop software exactly the way it was done before, in the environment they are familiar with. Since the solution is built upon an open and widely adopted standard, all available tools and resources related to web services can be leveraged and integrated when needed. The learning curve for adoption is therefore smooth and directly related to the integration needs of the user. On the other hand, the user has immediate access to all algorithms published by others without additional cost.

B. Creating or Hosting Web Services

From a purely technical point of view, the only requirement is that a web service be associated with a network address, hosting an interface that complies with WSDL. For instance, the web services hosted by the DAE platform are available at http://dae.cse.lehigh.edu/DAE/services/soap.

It should be noted that there is no need for the web services to be universally accessible. The WSDL server does not need to be accessible from other parts of the Internet and may perfectly be running on one's personal machine, on a local non-routable network, if there are no other intended users of the service.

As already stated before, web service servers can be made as complex as needed for specific task and integration requirements, but that is beyond the scope of this paper. However, in order to achieve the claims of contributing to broad reproducible experimental research, it is necessary that there is a clearly perceivable benefit from using this framework. Complex technical constraints are a hurdle to attain this. We therefore provide interested users with a straightforward way to set up, test and use their personal applications as web services. Full instructions and an installation kit are provided at http://sourceforge.net/projects/daeplatform/. The kit mainly consists of 3 PHP files and require no more than 15 lines of code to be modified to operate, mainly consisting in naming the right I/O variables and constructing the command string corresponding to the application to be launched.

To be publicly registered and referenced by the DAE platform, the process is only slightly more complicated. A web service must comply with a number of supplementary conditions, the most important being that its input and output parameters be defined in accordance with the DAE data model. However, there is no specific obligation for public web services to be registered in this way to still be available to the broader community. Since the protocols are open and standardized, other service providing repositories can be created and interact with the ones presented here.

C. Using and Accessing Web Services

While it remains perfectly possible to write web service aware programs that would interact through WSDL interfaces, there is no real need to program anything to use the document web services mentioned in the previous section. The only thing that is needed is a web service invocation tool like Taverna [START_REF] Oinn | Taverna: lessons in creating a workflow environment for the life sciences[END_REF].

Fig. 2 gives an example of what this looks like. Taverna allows the user to create input and output flows, and redirect them to and from web services, in a graphical click-and-play environment. The workflows can be saved into lightweight XML description files and shared with others. The tool also provides simple and straightforward operators like loops, parallelization, etc.

IV. CONCLUSION

In this paper we have advocated the use of web services to improve overall reproducibility of published document analysis results. In this section we will review the advantages this offers and how it can contribute to more generic and widespread benchmarking and evaluation protocols.

A. Availability, Access and Archiving

Providing software as a web service removes three major hurdles found with simply making source code available, without adding disadvantages, since all source code can still be provided (and should be promoted as good practice).

First, difficulties related to cross-platform issues disappear. Moreover, since the development overhead of making one's own code available as a web service is close to zero (and is most certainly far less than distributing and maintaining cross-platform code) there is a clear incentive to contribute programs through web services. Second, cases where intellectual property or commercial constraints have previously hindered sharing, can now be integrated for research and benchmarking, since all resources can remain under the control of those who provide the service. Finally, it becomes technically possible to keep operational and functional archives of legacy programs through virtualization techniques, since older code, running on obsolete operating systems or in discontinued environments can still be made available by having them run in virtual machines. The DAE platform, for instance, provides access to VirtualBoxhosted [START_REF] Watson | Virtualbox: bits and bytes masquerading as machines[END_REF] environments.

There is one catch to the approach presented in this paper, however: the dependency on network and computing resources. Other approaches, notably those consisting in distributing source code only, leave it to those who want to reproduce the results to prepare and execute the experiments, and therefore dispose of the required resources. In our case, it is the provider of the service who also provides execution resources. Partially centralized or distributed community resources may alleviate this.

B. Reproducibility, Benchmarking and Evaluation

The great gain that is achieved through this framework is full reproducibility for results, since the complete operational conditions of experiments are available, without bias related to implementation choices or parameter tuning. Complete experimental pipelines can be formalized and distributed with Taverna (or other, equivalent resources) and executed anywhere, without constraints. These pipelines (or workflows) can be re-appropriated by others and enhanced, challenged or transposed to other contexts, and through publication, contribute to sound and productive contradictory discussion of results and methods in general. By doing so, they become a cornerstone to the establishment of open, sharable benchmarking procedures in a transparent and reproducible way. Furthermore, it makes it much easier to conceive and distribute complex endto-end workflows as evaluation procedures for individual algorithms. For example, studying both the influence of individual OCR or layout analysis programs with respect to higher level interpretation tasks, like named entity detection, can be formalized and published as a workflow of generic web service components. It then becomes possible to replace individual algorithm contributions (e.g. a new OCR algorithm) without affecting the general experimental setup, and thus maintaining the objectivity of resulting performance measurements, without major re-engineering or software integration efforts.

C. Future Work

Currently ongoing work is related to the deployment and effective use of the framework for IAPR ICDAR and GREC contests [START_REF] Lamiroy | Document Analysis Algorithm Contributions in End-to-End Applications[END_REF]. This will provide, on the one hand, stress tests on the DAE infrastructure hosting some of the web services. The data generated will give useful information for further use and development. It will also provide user feedback on the usability and the efficiency of the approach. One of the interesting expected by-products of an effective use of the paradigm is that in a first stage, contributers are expected to simply provide a web service executing their software (either self-hosted or hosted on the DAE platform). In a second stage, when trying to interconnect various web services there will be need for specific contributions like format converters. It is expected that these converters, however, can be published as web services as well, thus contributing to a virtuous cycle of increased usability and usefulness and eventually users.

Other further extensions include a thorough evaluation of the impact on performance (throughput and bandwidth as well as overhead caused by the web service orchestrator) compared to direct execution. It should be emphasized that this framework is designed for research flexibility, and is probably not the optimal solution for high performance production environments. Also, there is an open question whether the standard synchronous WSDL approach is actually the best solution, or if in some cases, REpresentational State Transfer (REST) Web services would not be more appropriate.

A complete tutorial comprising examples and source code downloads can be found at http://tinyurl.com/ DAE-Web-Service-Tutorial.

Figure 1 .

 1 Figure 1. Overview of the DAE platform architecture

Figure 2 .

 2 Figure 2. Taverna workflow example, automatically taking random images from a DAE dataset, running different binarization algorithms.

Owing to space constraints, it is only possible for us to cite a small fraction of the many existing efforts to contribute shared resources for the use of the research community.

Acknowledgements

The authors wish to thank Lehigh students A. Borden and Q. Long for their technical contributions and research on Taverna. Bart Lamiroy was a visiting scientist at Lehigh University in 2010-2011. This work was conducted at the Computer Science and Engineering Department at Lehigh University and was funded through DARPA IPTO via Raytheon BBN Technologies.


Bart Lamiroy
email: bart.lamiroy@loria.fr

Daniel Lopresti
email: lopresti@cse.lehigh.edu

Tao Sun

Document Analysis Algorithm Contributions in End-to-End Applications: Report on the ICDAR 2011 Contest

Keywords: benchmark, web services, document analysis, performance evaluation

This contest aims to provide a metric giving indications on the influence of individual document analysis stages to overall end-to-end applications. Contestants are provided with a full, working pipeline which operates on a page image to extract useful information. The pipeline is built with clearly identified analysis stages (e.g. binarization, skew detection, layout analysis, OCR ...) that have a formalized input and output. Contestants are invited to contribute their own algorithms as an alternative to one or more of the initially provided stages. The evaluation measures the overall impact of the contributed algorithm on the final (end-of-pipeline) output.

I. INTRODUCTION

This is the first edition of a contest that tries to measure impact of individual, focused research contributions to more broad document analysis problems. In order to achieve this, we build upon two main concepts: the ability to express full scale document analysis workflows in a flexible and extensible way [START_REF] Lamiroy | An Open Architecture for End-to-End Document Analysis Benchmarking[END_REF] and the access to a data repository capable of tracking usage of the data and storing the resulting provenance so as to certify the results of the evaluation. [START_REF] Lamiroy | How Carefully Designed Open Resource Sharing Can Help and Expand Document Analysis Research[END_REF].

The expected impacts of this contest are:

1) It will allow the community, over time, to identify where significant contributions are taking place, where bottlenecks are occurring and what hard problems are still unsolved (significance bearing the meaning of "end-user application significant") . These measures will not be based on publication metrics and activity, but on tangible results of running algorithms. Contrary to usual contests, where contestants are trying to provide a solution to a whole process, here they can focus on one part of the process only, the overall evaluation being done for all combinations over all contributions. 2) Given the specific setup that is used (http://dae.cse. lehigh.edu), users will be able to build upon previous work and published state-of-the art algorithms with a known track record, thus, in time, creating greater re-usability, and promoting objective evaluation of published methods. This is due to the fact that the contest platform is built on flexible webservice enabled storage infrastructure that can host and interact with a wide variety of execution formats [START_REF] Lamiroy | An Open Architecture for End-to-End Document Analysis Benchmarking[END_REF]. Since, to compete, candidates need only to conform to specific input-output patterns, the entry level cost to interoperability, re-usability and sustainability is much lower.

3) The supporting infrastructure of the contest guarantees that contributions can be kept available over time and replayed on new datasets. This permits the effective monitoring of long term trends on the one hand, as well as extending the footprint of the contest to larger, more comprehensive end-to-end applications, always maintaining the knowledge of previous contributions.

II. 2011 SPECIFICS

Some of our intended goals for this contest can only be achieved over time. For the first edition, we have chosen to focus on the following points: Since this is the first time the contest is run, it convenes to scale it progressively, carefully assessing the feasibility of all goals. For this first edition, we have specifically focused on the following points:

1) The contest requires participants to expose their contributions as a web service (either hosted by themselves, either hosted by the contest organizers). This architecture is a testbed to evaluate whether a web service architecture may play a useful role in advancing document analysis research, especially by establishing how researchers will use such a system. Furthermore, while it is clearly an easy, flexible and ubiquitous way to create full pipeline prototypes, there is no doubt that custom developed and integrated applications will be more time/memory efficient. This contest will also be an opportunity to study the scalability in this domain. 2) Feedback from participants will provide useful input on the impact of this approach, beyond the vision we have outlined earlier, and highlight its benefits and its limitations.

3) The need to bootstrap an initial set of algorithms for the pipeline, as well as a deliberate attempt to inspire contributors to improve the available stages, makes the current contest environment somewhat simplistic. Indeed, the proposed pipeline (Binarization -Text Layout Segmentation -OCR -Named Entity Detection) is rather simplistic and may prove limiting in some ways. Its construction is a bet on the current maturity of state-of-the art DIA methods, and shall be extended in function of the received contributions and their results. As stated before, there is currently no real cartographic overview of how advances in the document analysis domain contribute to the quality of end-to-end applications.

III. CONTEST DESCRIPTION

For the contest, participants have been provided with a a full operational five-stage available from http://dae.cse.lehigh.edu/DAE/sites/default/files/ ICDARContest.t2flow. In order to execute the workflow, participants were invited to use Taverna [START_REF] Oinn | Taverna: lessons in creating a workflow environment for the life sciences[END_REF] The text files are parsed and named entities such as places, people and organizations are tagged as such. Participants were invided to provide access to implementations of one (or more) of the previous stages. Multiple entries for the same or for different categories were allowed. In order to test their contributions, participants were provided with standard, of-the-shelf, versions of each stage. Binarization was provided through the ImageMagick convert 1 program, a zero-effect segmentation web-service was provided (i.e. input images are simply echoed, without any segmentation), two OCR engines were made available: Ocrad2 and Tesseract 2.04 [START_REF] Smith | An overview of the tesseract ocr engine[END_REF] 3 , and the named entity detection software was the Stanford Named Entity Recognizer [START_REF] Finkel | Incorporating non-local information into information extraction systems by gibbs sampling[END_REF].

IV. CONTRIBUTIONS

Two research groups participated in the contest:

• the French EPITA Research and Development Laboratory 4 ,

• the Amercian NCI/CADD group, a research unit within the Chemical Biology Laboratory, part of the Molecular Discovery Program at the National Cancer Institute5 . EPITA contributed three algorithm implementations, all of which were hosted as web-services at their own facilities [START_REF] Lazzara | The scribo module of the olena platform: a free software framework for document image analysis[END_REF]:

• an implementation of the Sauvola binarization algorithm [START_REF] Sauvola | Adaptive document image binarization[END_REF] (EPITA_BI),

• a "generic" document text segmentation algorithm (EPITA_SEG),

• a specific document text segmentation algorithm that also participated in the ICDAR 2011 Historical Document Layout Analysis Contest (EPITA_HDOC). NCI/CADD contributed two algorithm implementations, both of which were hosted as web-services by the contest organizers in virtualized environments [START_REF] Filippov | Optical structure recognition software to recover chemical information: OSRA, an open source solution[END_REF]:

• a binarization algorithm (NCI_BI),

• a segmentation algorithm (NCI_SEG). These five contributions, combined with the provided default algorithms therefore offer three binarization choices, four segmentation options and two OCRs, resulting in 24 different ways of extracting the named entities. Figure 1 depicts the full Taverna workflow6 integrating all possible combinations that was used for running the contest.

V. CONTEST RESULTS AND ANALYSIS

The execution of the complete set 24 of combinations as represented in Figure 1 takes 16 minutes on average. Although this may seem slow, it is encouraging given the complexity of the setup and the inevitable overhead generated by the network data transfers, logging activities of the supporting platform etc.

We have run series of evaluations over groups of 30 or 40 images at a time, using the UNLV dataset [START_REF] Nartker | A preliminary report on UNLV/GT1: A database for ground-truth testing in document analysis and character recognition[END_REF] and its associated text transcription as ground-truth. We also conducted evaluations using a new paradigm capable of ovecoming the absence of formalized ground-truth [START_REF] Lamiroy | Precision and recall without ground truth[END_REF], but results were not yet sufficiently compiled at the time of this writing.

Figure 2 shows the overall F-Measure for all 24 combinations and the ranking obtained by ordering these results by decreasing order of F value. The numbering of the 24 combinations corresponds to a depth-first traversal of the execution tree depicted in Figure 1 with one notable inversion at the first level. Table I gives the full correspondance of indexes and execution paths.

The top five best ranked combinations are: From this finding and from the serrated shape of the graph we can draw the following conclusions.

• Tesseract significantly outperforms Ocrad and provides consistently higher overall performance. This is clearly illustrated in Figure 3, where we have projected the overall results of Figure 2 onto the two OCR dimensions.

• The four overall best ranked combinations involve the NCI_BI binarization program. These results are confirmed when projecting the overall results of Figure 2 onto either the binarization dimensions (Figure 4) or the segmentation dimensions (Figure 5). The NCI contributed algorithms consistently outperform the EPITA contributed algorithms, and the impact on the F-Measure is higher for the NCI binarization algorithm.

VI. CONCLUSION AND FURTHER WORK

The first conclusion of this contest is that the paradigm developed in [START_REF] Lamiroy | An Open Architecture for End-to-End Document Analysis Benchmarking[END_REF], [START_REF] Lamiroy | How Carefully Designed Open Resource Sharing Can Help and Expand Document Analysis Research[END_REF] is effective and usable: user contributions were integrated seamlessly, whether they were hosted within or without the DAE framework, regardless of their operating environment. Since it explicitely stores all intermediate results and conditions under which they were obtained, it opens the door to a wider range of uses, contributing to making tracability, reproducibility and comparison of experimental results easier.

Second, and more related to the evaluation of the contributions, the NCI Binarization algorithm is the contributed algorithm that had the most significant positive impact to the end-to-end application. It can be argued that the Tesseract OCR had an even bigger impact, but it was not a competing algorithm. It is also noteworthy to observe that for the Ocrad OCR binarization nor segmentation seem to have any impact on the final result. This might be related to the fact that the software possibly includes some filtering and layout functions, and would be interesting to investigate further. It is also important to stress that the full contest can be replayed and verified either by downloading the associated Taverna workflow files, or by directly querying the hosting server http://dae.cse.lehigh.edu where all execution information is available. As an example, the following SQL query will give all input and ouptut data that has been produced, and by which algorithms. Due to space constraints, this query has been slightly simplified.

Figure 1 .

 1 Figure 1. Full contest pipeline with contributed algorithms.

Figure 3 .

 3 Figure 3. OCR compared F-Measure and Ranking results for all possible combinations

Figure 4 .

 4 Figure 4. Binarization compared F-Measure and Ranking results for all possible combinations

Figure 5 .

 5 Figure 5. Segmentation compared F-Measure and Ranking results for all possible combinations

  . The individual stages of the workflow were hosted web-services on http: //dae.cse.lehigh.edu/DAE/services/soap and consisted of:

	Document Selection:
	Random document images are extracted from the
	contest data repository and provided as input to the
	next stage. No further assumption on image format
	or encoding is given.
	Document Binarization:
	Document images from the previous stage are
	treated to produce a binarized version as output.
	The output file can be in any open and commonly
	used bitonal format (.tif, pbm, ...)
	Layout Analysis/Text Localization:
	The bitonal images from the previous step are
	output either as a single document image, stripped
	from pictures, illustrations and, generally speaking,
	anything that is not text, or are output as a set
	of images, corresponding to the text blocs of the
	original document image.
	OCR:
	The previously produced documents images are
	transcribed into text. The output is a plain text
	file without any formating characters other than
	whitespace.
	Named Entity Detection:

  Full queries can be obtained from http://dae.cse.lehigh.edu/ DAE/?q=node/60.

	select dit_in.id data_item_in, dit_out.id
	data_item_out, alg.id algo_id from
	algorithm_run arun
	join algorithm_run_of arof on
	arof.algorithm_run_id = arun.id
	join algorithm_run_input arin on
	arin.algorithm_run_id = arun.id
	join data_item dit_in on
	dit_in.id = arin.data_item_id
	join algorithm alg on
	alg.id = arof.algorithm_id
	join algorithm_run_output arout on
	arout.algorithm_run_id = arun.id
	join data_item dit_out on
	dit_out.id = arout.data_item_id
	where alg.id in (182,183,143,162,125,222) and
	arun.start_time >= to_date('01/jun/2011',
	'dd/mm/yyyy') and
	arun.start_time < to_date('01/jul/2011',
	'dd/mm/yyyy')

http://www.imagemagick.org/script/convert.php

http://www.gnu.org/software/ocrad/

We deliberately offered acces to an older version of Tesseract, to allow contributions and comparisons with newer versions

http://www.lrde.epita.fr

http://cactus.nci.nih.gov/

Available for download at http://dae.cse.lehigh.edu/DAE/sites/default/ files/ICDARContestTotal.t2flow

Acknowledgements

Bart Lamiroy was a visiting scientist at Lehigh University in 2010-2011 at the Computer Science and Engineering Department. This work was funded through DARPA IPTO via Raytheon BBN Technologies.